[Algorithm] Priority Queue (우선순위 큐)

기본적으로 큰 값이 가장 맨 위에 오도록 queue를 쌓는다.

 

priority_queue의 구조는 priority_queue<자료형, 구조체, 비교함수> 이다.

 

따라서 아래와 같이 코드를 짜면 된다. (C++기준)

#include <queue>

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

less<int> : 가장 큰 값이 맨 위에 온다.

greater<int> : 가장 작은 값이 맨 위에 온다.

 

만약 직접 구현한 구조체에 해당하는 비교함수를 쓰고싶다면 아래와 같이 사용하면 된다.

 

#include <queue>

struct node{
    int x, y, cost;
    node(int x, int y, int cost):x(x), y(y), cost(cost){}
};

struct cmp{
    bool operator()(node a, node b){
        return a.cost > b.cost;
    }
};

priority_queue<node, vector<node>, cmp> q;

cmp라는 구조체를 만들고 비교 연산자 함수를 정의하여 priority_queue의 비교함수로 사용한다.

참고로 위 코드는 오름차순 정렬(작은 값 부터 나옴)이다.

큰 값 부터 나오게 하려면 a.cost < b.cost 로 수정하면 된다.