우선순위 큐(Priority Queue)는 우선순위가 지정된 요소들의 컬렉션을 저장하는 추상 자료형(ADT, Abstract Data Type)입니다. 각 요소는 우선순위에 따라 삽입과 삭제가 이루어지며, 가장 높은 우선순위를 가진 요소가 언제든지 먼저 제거될 수 있습니다.
일반적인 스택(Stack), 큐(Queue), 리스트(List)와 달리, 우선순위 큐는 요소를 선형적인 위치 순서로 저장하지 않습니다. 대신 각 요소의 우선순위 값을 기준으로 내부적으로 정렬하여 관리합니다. C++의 STL에서 우선순위 큐는 기본적으로 최대 힙(Max Heap) 구조로 구현되어 있어, 가장 큰 값이 항상 맨 앞(top)에 위치하게 됩니다.
우선순위 큐의 주요 멤버 함수
C++에서 priority_queue가 지원하는 핵심 함수들은 다음과 같습니다.
- size() − 우선순위 큐에 포함된 요소의 개수를 반환하여 큐의 크기를 계산할 때 사용됩니다.
- empty() − 우선순위 큐가 비어 있으면 true를, 그렇지 않으면 false를 반환합니다.
- push(element) − 새로운 요소를 우선순위 큐에 삽입합니다. 삽입 후 자동으로 우선순위에 맞게 정렬됩니다.
- top() − 우선순위 큐에서 최우선 순위(기본 설정 시 가장 큰 값)의 요소를 반환합니다. 큐가 비어 있는 경우 호출하면 정의되지 않은 동작(Undefined Behavior)이 발생할 수 있습니다.
- pop() − top() 함수가 참조하는 최우선 요소를 큐에서 제거합니다. 이때 제거된 값은 반환되지 않습니다.
우선순위 큐 동작 알고리즘
시작
Step 1-> 우선순위 큐의 요소를 출력하는 함수 선언
void display(priority_queue <int> Pq)
priority_queue <int> que = Pq 로 복사본 생성 및 초기화
While (!que.empty()) 반복
que.top() 호출하여 최상단 요소 출력
que.pop() 호출하여 요소 제거
종료
Step 2-> main() 함수에서
priority_queue <int> Pq 객체 생성
push()를 호출해 요소 삽입 (예: Pq.push(1))
display(Pq) 호출하여 전체 요소 출력
Pq.size() 호출하여 큐의 크기 확인
Pq.top() 호출하여 최상단 요소 출력
Pq.pop() 호출하여 요소 제거
display(Pq) 호출하여 변경된 큐 출력
종료C++ 예제 코드
#include <iostream>
#include <queue>
using namespace std;
void display(priority_queue <int> Pq) {
priority_queue <int> que = Pq;
while (!que.empty()) {
cout << '\t' << que.top();
que.pop();
}
}
int main () {
priority_queue <int> Pq;
Pq.push(1);
Pq.push(3);
Pq.push(5);
Pq.push(7);
Pq.push(9);
cout << "The priority queue is : ";
display(Pq);
cout << "\nPrioriy queue size using size() : " << Pq.size();
cout << "\nFirst element of priority queue using top(): " << Pq.top();
cout << "\nremoving element using pop() : ";
Pq.pop();
display(Pq);
return 0;
}실행 결과
The priority queue is : 9 7 5 3 1 Prioriy queue size using size() : 5 First element of priority queue using top(): 9 removing element using pop() : 7 5 3 1
코드 해설
위 예제에서 1, 3, 5, 7, 9를 순서대로 push() 했지만, 출력 결과는 9 7 5 3 1로 내림차순으로 정렬되어 나타납니다. 이는 C++의 기본 priority_queue가 최대 힙(Max Heap) 방식으로 동작하기 때문입니다. 즉, 입력 순서와 무관하게 항상 가장 큰 값이 top에 위치합니다.
top() 함수를 사용하면 현재 최우선 요소인 9를 확인할 수 있으며, pop()을 호출한 후에는 해당 요소가 제거되어 남은 요소들이 7 5 3 1 순서로 출력됩니다.
마무리
우선순위 큐는 작업 스케줄링, 다익스트라(Dijkstra) 최단 경로 알고리즘, 허프만 코딩(Huffman Coding) 등 우선순위 기반 처리가 필요한 다양한 분야에서 활용됩니다. 내부적으로 힙 구조를 사용하기 때문에 삽입과 삭제 연산은 O(log N)의 시간 복잡도를 가지며, 최상단 요소 조회는 O(1)로 매우 효율적입니다. C++ STL의 priority_queue를 잘 활용하면 이러한 알고리즘 문제들을 간결하고 효율적으로 해결할 수 있습니다.