[C++] priority_queue

힙으로 구현된 큐로, 기본적으로 내림차순으로 정렬된다(top이 가장 큰 값)

 

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

int main()
{
    // 내림차순 정렬
    priority_queue<int> q;
    // or
    priority_queue<int, vector<int>, less<int>> q2;
    
    // 오름차순 정렬
    priority_queue<int, vector<int>, greater<int>> q;
    
    q.top() // 가장 위에 위치한 값을 리턴
    q.pop() // 가장 위에 위치한 값을 삭제
    q.empty() // 큐가 비있는지를 리턴(bool)
    q.push(a) // 큐에 원소를 푸시
}

 

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

struct comp
{
    bool operator()(pair<int, int> &a, pair<int, int> &b)
    {
        if (a.first == b.first)
            return a.second > b.second;
        return a.first > b.first;
    }
};

int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> q;
}

직접 비교 함수를 지정해 줄 수도 있다

(사실 위의 경우는 굳이 직접 지정해주지 않고 greater<pair<int, int>>를 넣어줘도 인자가 두 개면 첫번째 인자 기준으로 오름차순 정렬 후, 첫번째 인자가 같다면 두 번째 인자 기준으로 오름차순 정렬된다)