priority queue 비교 연산자 구현

사용자 정의 비교 연산자 구현

• 우선순위 큐 선언

#include <queue>
using namespace std;
int main(){
  priority_queue<int, vector<int>, compare> pq; // 자료형 int, 컨테이너 vector, 사용자 정의 비교연산자 compare

 

• 비교 연산자 구현

1. 정수를 오름차순으로 정렬하는 비교 연산자

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

• 우선순위 큐 내부에 새로운 자료가 들어가면 자신의 부모 노드와 크기를 비교하면서 조건에 따라 swap
• 위 코드에서 a는 부모 노드, b는 현재 노드
• 만약 a가 b보다 크다면 true를 return에서 swap을 진행함
• 이를 반복하면 조상 노드는 가장 작은 원소가 차지하게 됨

2. 정수를 내림차순으로 정렬하는 비교 연산자

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

• 의 코드는 반대로 a가 b보다 크면 false 리턴. 따라서 swap 안함
• 조상 노드는 가장 큰 원소가 차지
• compare를 구현하기 위한 핵심은, 두 자료를 비교했을 때 swap을 해줄 것인지 말 것인지 결정하는 것

3. pair의 second를 기준으로 오름차순 정렬

struct compare{
    bool operator()(pair<int, int> a, pair<int, int> b){
        return a.second > b.second;
    }
};
int main(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
}