[이론] 우선순위 큐 (Priority Queue)

우선순위 큐란?

---

일반적인 큐는 선입선출(FIFO) 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되는데, 우선순위 큐는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다

우선 순위 큐는 최소 우선 순위, 최대 우선 순위 2가지로 구분할 수 있다

• 최소 우선순위 큐 : 가장 우선 순위가 낮은 요소를 삭제
• 최대 우선순위 큐 : 가장 우선 순위가 높은 요소를 삭제

 

스택 vs 큐 vs 우선순위 큐

자료구조	삭제되는 요소
스택	가장 최근에 들어온 데이터
큐	가장 먼저 들어온 데이터
우선순위 큐	가장 우선순위가 높은 데이터

 

 

우선순위 큐의 추상 자료형(ADT)

 

객체 : n개의 element형의 우선순위를 가진 요소들의 모임

연산

• create() ::= 우선순위 큐를 생성
• init(q) ::= 우선순위 큐 q를 초기화
• is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
• is_full(q) ::= 우선순위 큐 q가 가득 찼는지 검사
• insert(q,x) ::= 우선순위 큐 q에 요소 x를 추가
• delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다
• find(q) ::= 우선 순위가 가장 높은 요소를 반환한다

 

우선순위 큐의 구현 방법

배열, 연결 리스트, 히프 등을 이용하는 방법이 있다

---

배열(Array)을 사용한 구현 방법

1. 요소를 정렬하지 않고 배열에 넣는 경우 
   • 삽입 연산의 시간복잡도 : O(1) 
     • 배열의 맨 끝에 새로운 요소를 추가하면 됨
   • 삭제 연산의 시간복잡도 : O(n) * O(n) -> $O(n^2)$
     • 가장 우선순위가 높은 요소를 찾아야 하는데, 정렬이 되어 있지 않으므로 탐색에 O(n)의 시간복잡도를 가지게 됨
     • 삭제 후, 뒤에 있는 요소들을 앞으로 이동시켜야 하므로 이동에 O(n)의 시간복잡도를 가진다
2. 요소를 정렬하고 배열에 넣는 경우
   • 삽입 연산의 시간복잡도: O(logn) * O(n) -> $O(nlogn)$ 
     • 새로운 요소 삽입 시, 적절한 삽입 위치를 찾기 위한 탐색 과정이 필요함
     • 정렬된 배열이므로 이분(이진) 탐색을 수행하면 탐색에 O(logn)의 시간복잡도를 가진다
     • 삽입 위치를 찾은 다음에, 삽입 위치 뒤에 있는 요소들을 이동시켜 빈자리를 만들어야 하므로 이동에 O(n)의 시간복잡도를 가진다
   • 삭제 연산의 시간복잡도 : O(1)
     • 숫자가 높은 것이 우선 순위가 높다고 가정하면, 맨 뒤 요소를 삭제하면 되므로 O(1)의 시간복잡도를 가진다

 

연결 리스트(linked list)를 사용한 구현 방법

배열의 경우와 크게 다르지 않은데, 정렬된 상태와 정렬되지 않은 상태로 연결 리스트를 사용할 수 있다

단, 배열과 다르게 연결리스트에서는 삽입/삭제 시 다른 노드를 이동할 필요가 없으므로, 배열의 시간복잡도에서 이동에 필요한 시간복잡도는 계산하지 않은 값과 같다

 

히프(Heap)를 사용한 구현 방법

히프는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 특별히 만들어진 자료구조로, 느슨한 정렬 상태를 유지한다

히프는 완전히 정렬된 것은 아니지만 전혀 정렬이 안된 것도 아닌 상태를 유지하는데, 이런 상태를 이용하여 우선순위 큐를 구현한다

히프의 개념 및 자세한 구현 방법은 아래 게시글에서 다루니 좀 더 궁금하다면 참고하면 좋다

https://codingsmu.tistory.com/89?category=871719 

[이론] 히프(Heap)

 

위의 게시글에서 자세히 다루겠지만, 히프의 효율을 $O(logn)$으로 다른 두 방법보다 훨씬 효율적이다 좀 더 자세한 비교는 아래 표를 참고하도록 하자

표현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(1)	O(1)
히프	O(logn)	O(logn)