C++ 우선순위 큐(priority_queue) 완벽 정리: 개념부터 STL 활용까지

큐(queue) 자료구조는 선입선출(FIFO, First In First Out) 방식으로 동작하는 구조로 널리 알려져 있습니다. 큐는 용도에 따라 다양한 변형 형태로 발전했는데, 대표적인 것이 바로 덱(Deque)과 우선순위 큐(Priority Queue)입니다.

이번 글에서는 큐의 변형 중 하나인 우선순위 큐에 대해 자세히 살펴보겠습니다. 우선순위 큐에서는 큐에 저장되는 각 요소가 고유한 우선순위를 가지며, 요소를 삽입할 때 반드시 우선순위 값을 함께 지정해야 합니다. 삭제 연산이 수행될 때는 항상 우선순위가 가장 높은 요소가 먼저 제거됩니다.

우선순위 큐를 구현하는 가장 손쉬운 방법 중 하나는 힙(heap) 자료구조를 활용하는 것입니다. 힙은 최댓값 또는 최솟값을 빠르게 추출할 수 있는 완전 이진 트리 기반 구조로, 우선순위 큐의 내부 구현에 매우 적합합니다.

그럼 C++ STL로 작성된 우선순위 큐 예제 코드를 확인해 보겠습니다. 아래 예제에서는 값 자체를 우선순위 기준으로 사용하므로, 값이 클수록 더 높은 우선순위를 갖게 됩니다.

알고리즘

삽입(insert)

insert(key, priority):
Begin
   힙의 마지막 위치에 key 삽입
   우선순위를 기준으로 배열을 재정렬(heapify)
End

삭제(delete)

delete():
Begin
   item := 루트(root) 요소
   root := 배열의 마지막 요소
   우선순위를 기준으로 배열을 재정렬(heapify)
   item 반환
End

C++ 예제 코드

#include <iostream>
#include <queue>
using namespace std;

void dequeElements(priority_queue <int> que) {
   priority_queue <int> q = que;
   while(!q.empty()){
      cout << q.top() << " ";
      q.pop();
   }
   cout << endl;
}

int main() {
   priority_queue <int> que;
   que.push(10);
   que.push(20);
   que.push(30);
   que.push(5);
   que.push(1);
   cout << "현재 큐에 저장된 요소 : ";
   dequeElements(que);
   cout << "큐의 크기 : " << que.size() << endl;
   cout << "최상단(top) 요소 : " << que.top() << endl;
   cout << "큐에서 삭제 : ";
   que.pop();
   dequeElements(que);
   cout << "큐에서 삭제 : ";
   que.pop();
   dequeElements(que);
}

실행 결과

현재 큐에 저장된 요소 : 30 20 10 5 1
큐의 크기 : 5
최상단(top) 요소 : 30
큐에서 삭제 : 20 10 5 1
큐에서 삭제 : 10 5 1

정리

실행 결과를 보면 입력 순서(10, 20, 30, 5, 1)와 무관하게, priority_queue는 항상 가장 큰 값이 top에 위치하며 pop()을 호출할 때마다 내림차순 순서로 요소가 제거되는 것을 알 수 있습니다. 이는 내부적으로 최대 힙(max heap)이 사용되기 때문입니다. 만약 오름차순(최소 힙) 동작이 필요하다면 priority_queue<int, vector<int>, greater<int>>처럼 비교 함수자(comparator)를 지정하면 됩니다.