8. Priority Queue

priority_queue(우선순위 큐)는 스택, 큐와는 또 다른 컨테이너 어댑터로, 원소들이 특정 기준에 따라 자동으로 정렬된다는 특징이 있다. 헤더파일 <queue>를 인클루드하면 사용이 가능하다. priority_queue 클래스는 <bits/stl_queue.h>에 정의되어 있다. 별도의 <priority_queue>나 <bits/stl_priority_queue.h>같은 헤더파일은 존재하지 않는다. 또한 기본 컨테이너로 vector를 사용한다.

 

우선순위 큐의 선언 방법은 스택, 큐의 선언 방법과 같다.

priority_queue<int>p;

이렇게 선언하면 비어 있는 우선순위 큐가 생성된다.

스택과 큐를 설명할 때는 언급하지 않았지만, 컨테이너 어댑터를 선언할 때 <> 안에는 자료형 외에 다른 내용이 더 들어갈 수 있다. 자료형 뒤에 그 컨테이너 어댑터에서 사용할 컨테이너를 명시할 수 있고, 우선순위 큐의 경우 그 뒤에 그 우선순위 큐에서 사용할 정렬 기준을 명시할 수 있다. 대부분은 이것들을 생략하고 기본 설정에 맞게 사용하기 때문에 볼 일은 많이 없지만 알아 두는 것이 좋다.

 

우선순위 큐의 멤버 함수는 스택의 멤버 함수와 유사하며 기능도 거의 같다.

p.push(x);	p에 x를 삽입한다.
p.pop();	p의 맨 위 원소를 삭제한다.
p.top();	p의 맨 위 원소를 참조한다.
p.size();	p에 들어 있는 원소의 개수를 반환한다.
p.empty();	p가 비었는지 확인한다.
p.emplace(x);	p에 x를 삽입한다.
p.swap(k);	p와 k를 맞바꾼다.

우선순위 큐의 맨 위 원소는 그 우선순위 큐의 정렬 기준에 따라 원소를 정렬했을 때 맨 앞에 오는 원소를 말한다. 기본 정렬 기준은 값의 내림차순(less<T>)이고, 이때 우선순위 큐의 맨 위 원소는 가장 값이 큰 원소가 된다. 또한 스택, 큐와 마찬가지로 원소를 모두 삭제하는 내장 함수가 존재하지 않는다.

 

우선순위 큐가 쓰이는 대표적인 알고리즘은 Dijkstra이며, 그밖에도 다양한 범위에 범용적으로 사용된다.

 

[연습문제]

 

BOJ 11279. 최대 힙 (Silver II)

우선순위 큐를 이용하면 쉽게 해결할 수 있다. 우선순위 큐는 힙으로 구성되므로 힙을 이해하면 우선순위 큐를 이해하기 쉽게 된다.

 

BOJ 1927. 최소 힙 (Silver I)

원소를 우선순위 큐에 넣을 때 부호를 바꿔서 넣고, 출력할 때도 부호를 바꿔서 출력하면 된다. 이렇게 하면 우선순위 큐를 priority_queue<int, vector<int>, greater<int>>와 같이 복잡하게 선언하지 않아도 된다.

 

BOJ 1655. 가운데를 말해요 (Gold II)

지금까지 말한 수들 중 큰 수 절반과 작은 수 절반을 나누어서 두 우선순위 큐에 저장하는 상태를 유지하면 각각의 상태에 대한 중앙값을 빠르게 구할 수 있다.

 

→ solved.ac tag: priority_queue