c++ priority_queue에서 comparator 선언해주는 방법

class Prove{ public : int pos, cost, time; Prove(int nposition, int ncost, int ntime){ pos = nposition; cost = ncost; time = ntime; } }; class mycomparison { public: bool operator() (const Prove& a, const Prove& b) const { return a.time > b.time; } }; priority_queue<Prove, vector<Prove >, mycomparison> mypq;

위의 Prove class는 내가 문제를 풀기 위해 임의로 만든 것이기 떄문에 무시해도 된다.

만약 int인 priorityqueue를 만들고 싶다면

priority_queue<int, vector<int>, mycomparison>

으로 선언하면 된다.

여기서 세가지 인자가 들어가는데 하나는 자료형, 자료형을 저장하는 자료구조, 그리고 비교연산이다

자료구조는 별일 없으면 vector로 선언하면 된다.

mycomparison이 비교 연산을 하는 것인데 이건 class로 선언해줘야 한다.

algorithm 라이프러리에 sort를 해결할 때는 일반 함수처럼 선언해서 해결하면 되었었는데 priority_queue는 그렇지 않았다

그리고 여기서 heap을 어떤 순서로 나열하느냐는 일반적인 compare와 다르다

sort에서는 오름 차순으로 하려면

compare(int a, int b) return a < b;

이렇게 했는데 priority_queue에서는

compare(int a, int b) return a > b;

로 해주어야 한다.

heap만의 특성이라 그런가 보다