[STL] 우선순위 큐 priority_queue

우선순위 큐 priority_queue는 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 설정되어 있다. 우선순위 큐는 자료구조 Heap으로 구현되어 있어 pop과 push를 할 때 마다 정렬된다.

 

priority_queue<int> pq; 이렇게 쓰면 내림차순으로 queue에 push되고 

priority_queue<int, vector<int>, greater<int>> pq; 이렇게 쓰면 오름차순으로 queue에 push된다.

 

<메소드>

• push() 
• pop() top의 원소 제거
• top() 우선순위 큐에서 top에 있는 원소 즉 우선순위가 높은 원소를 반환
• empty() 비어있으면 true를 반환하고 그렇지 않으면 false를 반환
• size() 원소의 수를 반환

내림차순으로 queue에 push

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;

    pq.push(5);
    pq.push(3);
    pq.push(2);
    pq.push(1);
    pq.push(4);

    while (!pq.empty()) {
        cout << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

출력

5
4
3
2
1

 

오름차순으로 queue에 push

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int, vector<int>, greater<int>> pq;

    pq.push(5);
    pq.push(3);
    pq.push(2);
    pq.push(1);
    pq.push(4);

    while (!pq.empty()) {
        cout << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

출력

1
2
3
4
5