[Algorithm] c++, priority queue, min heap, ascending, 오름차순

기본인데도 자꾸 까먹어서 기록하는 것...

---

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

prioriry_queue는 함수 타입을 받는게 아니라, 비교 객체의 타입을 템플릿 인자로 받는다. 
그러므로 오름차순 정렬을 하고 싶으면 다음의 2개의 방법을 사용할 수 있다. 
1. 구조체 + operator() 사용

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

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

• cmp는 type이기 때문에 priority_queue 템플릿 인자로 넘길 수 있다.
• 기본 constructor가 있기 대문에 내부에서 cmp()를 자동으로 생성할 수 있다.
• operator(): 함수 호출 연산자 오버로딩. cmp 객체를 함수처럼 호출 가능하게 만들어주는 역할이다. 
  • ex: cmp comp; 로 선언하고 bool result = comp({1,5}, {2,3}); 라고 마치 함수처럼 호출할 수 있게 해준다.

2. 람다 + decltype() 사용

auto cmp = [](const vector<int>& a, const vector<int>& b) {
    return a[1] > b[1];  // 2번째 요소 기준 오름차순
};

priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);

• decltype(): 타입을 추론해주는 문법
• pq(cmp): 비교함수 cmp를 인자로 넘겨서 priority queue 생성