C++ STL:: priority queue

제대로 쓸줄 알면 c++의 sort같은것 없이도 활용도 높은 작업들을 많이 할 수 있을 것 같다.

예를 들면 알고리즘 문제풀때라던지

 

우선순위 큐는 사용방법이 priority_queue<자료형, 구현체, 비교 연산자>로 정의된다.
예를 들어보자.

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int main(){
 
    // priority_queue
    priority_queue< int, vector<int>, less<int> > pq;
    // or priority_queue<int> pq;
 
 
    // push(element)
    pq.push(5);
    pq.push(2);
    pq.push(8);
    pq.push(9);
    pq.push(1);
    pq.push(14);
 
 
    // pop()
    pq.pop();
    pq.pop();
 
 
    // top();
    cout << "pq top : " << pq.top() << '\n';
 
 
    // empty(), size()
    if(!pq.empty()) cout << "pq size : " << pq.size() << '\n';
 
 
    // pop all
    while(!pq.empty()){
        cout << pq.top() << " ";
        pq.pop();
    }
 
    cout << '\n';
 
    return 0;
 
}

<실행결과>

pq top : 8
pq size : 4
8 5 2 1

 

큰 숫자들이 위에 차곡차곡 정렬이 되고, pop을 실행하면 제일 큰 숫자가 나오게 되는 것이다.

큰 숫자들 먼저 처리하고 싶을땐 그냥 priority_queue<int> 로 간단하게 만들 수 있다.

 

 

그렇다면 저 위에서 

priority_queue< int, vector<int>, less<int> > pq;

를

priority_queue< int, vector<int>, greater<int> > pq;

라고 바꾸면 어떻게 될까??

 

<실행결과>

pq top : 5
pq size : 4
5 8 9 14

 

예상했던 대로 작은 숫자 순서대로 위에 쌓이며 pop도 작은 숫자가 튀어나오는 꼴임.