[C++] 우선순위 큐 priority_queue

개요

• C++ queue 라이브러리에서 제공
• push 수행 시 원소를 일반적인 큐와 달리 특정한 우선순위에 배정하는 자료구조
• 우선순위 큐와 동일한 원리로 자료구조 Heap 존재
• Dijkstra 알고리즘에 자주 활용

 

활용

#1 int 원소를 가지는 힙 (heap)

• 가장 큰 원소가 top에 위치

#include <queue>

...

priority_queue <int> PQ;

PQ.push(3);
PQ.push(1);
PQ.push(2);

cout << PQ.top(); // 3

 

#2 pair<int, int> 원소를 가지는 '최소' 힙 (min heap)

• 아래 코드와 같이 <A, vector<A>, B<A>> 형태로 B의 우선순위 적용 가능
• 첫 번째 int의 값이 가장 작은 원소가 top에 위치

#include <queue>

...

priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;

PQ.push(make_pair(3, 999));
PQ.push(make_pair(1, 999));
PQ.push(make_pair(2, 999));

cout << PQ.top().first; // 1

 

참고 자료

std::priority_queue - cppreference.com