c++) priority_queue cmp 구조체 정의

https://en.cppreference.com/w/cpp/container/priority_queue

std::priority_queue - cppreference.com

 

우선순위큐는 디폴트로 큐의 top에 큰 값이 오도록 정렬한다. (max heap)

top에 작은 값이 오도록 정렬하려면 (min heap) 따로 compare 구조체를 정의해도 되고,

세 번째 파라미터에 greater<> 함수를 써도 된다.

 

 

하지만 compare 구조체를 정의해서 사용하면 sort와 마찬가지로 내가 원하는대로 자동 정렬되도록 사용할수 있다.

첫 인자인 T는 구조체를 의미한다.  우선순위큐에 넣을 자료형을 써주면 된다. 

두번째 인자인 컨테이너는 vector<T>가 들어간다. vector<첫번째 인자> 이런식으로 써준다.

세번째 인자가 내가 정의해서 쓸 compare 구조체다.

 

---

pair<int,int> 가 들어가는 priority_queue

우선순위큐 선언은 다음과 같이 해주면 된다 

priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;

첫번째 인자에 우선순위큐에 넣을 pair<int,int>

두번째 인자에 vector<T>인 vector<pair<int,int>> 

세번째 인자에 compare 구조체 

 

pair의 두번째 요소 기준 오름차순 정렬하도록 compare 구조체 정의

struct cmp
{
    bool operator()(const pair<int,int> &a, const pair<int,int> &b)
    {
        return a.second > b.second;
    }
};

 

벡터의 sort 의 cmp 함수와 대소 비교가 반대인 이유는, 

우선순위 큐는 우선순위 를 비교하기 때문이다.

여기서는 a가 기존 우선순위 큐의 top에 존재하는 값이고, b가 새로 push 한 값이라고 보면 된다.

a = {1,3}, b = {2,1} 라고 하면 b의 second값이 더 작기 때문에 a.second > b.second 는 true 를 반환하고

b가 우선순위를 갖는다고 보면 된다. 

 

출력 결과 

 

 

 

아래와 같이 세번째 파라미터에 그냥 greater<>이나 less<>를 줘도 무관하다.

 

---

vector<int>가 들어가는 priority_queue

 

우선순위 큐 선언

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

 

compare 구조체 정의 (vector[1] 기준 오름차순 정렬)

struct cmp
{
    bool operator()(const vector<int> &a, const vector<int> &b)
    {
        return a[1] > b[1];
    }
};

 

출력 결과