우선순위 큐(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