[자료구조] 우선순위 큐 (Priority Queue)

개념

우선순위 큐(priority queue)는 임의의 순서로 입력된 우선순위된 원소들을 저장하고 우선순위에 따라 출력하는 추상 데이터 타입이다. 즉 언제든지 저장된 원소들 중 가장 우선순위가 높은 원소가 삭제된다.

성질

우선순위 큐는 항상 적용될 수 있는 비교 규칙이 필요하다. ≤으로 표기되는 비교 규칙이 항상 적용되기 위해서는 전체 순서(total order) 관계를 만족해야 한다. 전체 순서 관계는 모든 쌍의 두 키에 대하여 다음과 같은 특성을 만족한다.

• 반사성(Reflexive property): $k \le k$
• 비대칭성(Antisymmetric property): 만약 $k_{1} \le k_{2}$ 이고 $k_{2} \le k_{1}$ 일 경우, $k_{1}=k_{2}$
• 이행성(Transitive property): 만약 $k_{1} \le k_{2}$ 이고 $k_{2} \le k_{3}$ 일 경우, $k_{1} \le k_{3}$

위와 같은 세 가지 특성을 갖는 모든 비교 규칙은 모순되지 않는다. 이러한 규칙은 한 집합에 대해서 선형 순위 관계를 정의한다. 따라서 유한한 원소들에 대하여 전체 순서가 정의되어 있으면, 최소값($k_{\min}$)의 개념이 정의된다. 최소값은 집합의 모든 값 $k$에 대하여 $k_{\min} \le k$를 만족한다.

추상 데이터 타입(ADT)

• push(val): 원소 val을 큐에 삽입한다.
• top(): 최소값을 반환한다.
• pop(): 큐에서 최소값을 삭제한다.
• size(): 큐의 원소의 개수를 반환한다.
• empty(): 큐가 비어있으면 true를 그렇지 않으면 false를 반환한다.

구현

C++에서 array, priority_queue 등을 이용해 구현할 수 있다.