우선순위 큐(priority queue)

stl queue와 동일하게 #include <queue>를 해주고 다음처럼 코딩하면..

priority_queue<int> qq;
qq.push(2);
qq.push(5);
qq.push(1);
while (qq.empty() == 0) {
    printf("%d ", qq.top()); qq.pop();
}

 

5,2,1 순으로 표시된다.

queue에 넣는 순서가 아니라 값 기준으로 정렬되면서 들어가는 것이다.

queue와의 API적인 차이점은 front()대신 top()이 쓰인다는 점

 

이렇게 되는데는 max heap과 관련이 있다.

 

내림차순이 아닌 오름차순으로 정렬하려면 다음처럼 queue선언을 바꿔주면 된다.

priority_queue <int, vector<int>, greater<int> > qq;
 

필요이상으로 복잡해진점은 그냥 그러려니 하고 넘어가자--;; C++은 이런 측면으론 결함언어이다.

만약 큐에 들어가는 값이 0보다 크다는것이 보장된다면 위처럼 복잡한 선언을 해주는대신 음수값을 넣어주는 방법도 있다.

 

이걸 쓸경우 queue하나에 넣고 빼는데 O(log N)으로 생각하면 된다.

즉 N루프안에 priority_queue연산을 넣어도 O(N log N)정도에 돌릴 수 있다는 이야기

O(N^2)가 안될때 고려해볼 만 하다.

 

관련문제 리스트

코드포스 Playlist

 

사용자정의 정렬함수 사용

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

bool compareJobs(const pair<int, int>& a, const pair<int, int>& b) {
    if(a.first == b.first)
        return a.second > b.second; // 요청 시각이 빠른 게 우선 (최소 힙이므로 > 사용)
    return a.first > b.first;
}

int main() {
    // decltype(&compareJobs) 를 이용하여 comparator의 타입을 지정
    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        decltype(&compareJobs)
    > pq(&compareJobs);

    pq.push({10, 0});
    pq.push({5, 1});
    pq.push({15, 2});

    while (!pq.empty()) {
        auto top = pq.top();
        cout << "소요시간: " << top.first << ", 요청 시각: " << top.second << "\n";
        pq.pop();
    }
    return 0;
}

decltype을 적어줘야 하는것 빼고는 std::sort의 비교함수와 비슷한 느낌으로 쓸 수 있다.

근데 이거 2가지 치명적인 주의사항이 있네;

첫번째는, 아래 빨간색 부분을 실수하기 쉽다는거다. &안붙여도 실행은 되는데 null오류가 나고, pq뒤에 괄호를 생략하거나 &를 생략해도 마찬가지다;;

    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&compareJobs)> pq(&compareJobs);

두번째는 priority_queue의 경우 desc정렬이 기본이라 기본정렬의 기호가 반대라는 것이다;;;

std::sort인 경우일때 비해서 아래 괄호 방향을 거꾸로 해줘야 한다.

bool compare2(const vector<int>& a, const vector<int>& b) {
  return a[1] > b[1]; // 오름차순을 원하는건데 괄호방향이 std비교함수와 반대임
}