[C++] 우선 순위 큐 정렬 방법 변경

우선순위 큐는 기본적으로 내림차순으로 정렬한다.

priority_queue<T, Container<T>, Compare> pq;
priority_queue<T>;

평소에 두번째 줄로 많이 이용했는데 첫번째 줄이 우선순위 큐의 원형이다.

내부 컨테이너는 힙을 이용하기 때문에 compare 디폴트는 내림차순 정렬을 하는 비교 함수이다.

T자리에 pair가 들어가면 디폴트로 첫번째 인자 기준 내림차순, 같다면 두번째 인자 기준 내림차순으로 정렬한다.

 

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

벡터와 내림차순을 디폴트로 할 때는 짧게 써도 상관 없지만 다른 유형을 사용하고 싶다면 원형을 써줘야 한다.

세번째 인자를 greater로 바꿔 오름차순으로 정렬하는 우선 순위 큐이고 pair을 비교할 때도 동일하게 적용된다.

오름차순도 pair가 들어가면 첫번째 인자 기준 오름차순, 같다면 두번째 인자 기준 내림차순으로 정렬한다.

 

struct compare{
    bool operator()(int a, int b){
        return a>b;
    }
};

구조체를 이용해 우선순위 큐를 어떻게 정렬할지 커스텀으로 만들 수 있다. 우선순위 큐는 힙 구조인데 a는 부모노드이고

b는 자식노드이다. a가 b보다 클 경우 true를 반환하고 swap한다. 이 행위를 swap이 일어나지 않을 때까지 반복해 결국 조상 노드는 가장 작은 원소가 된다. 이게 오름차순(최소 힙)이고 내림차순(최대 힙)은 반대다. ()연산자를 쓰는 이유는

함수 객체를 쓰는 거라는데 자세히는 모르겠다.