008_우선순위 큐 (std::priority_queue)

우선순위 큐 (std::priority_queue)

우선순위 큐 (priority_queue)는 컨테이너 어댑터(Container Adapter) 중 하나이다. (vector 기반)

기본값으로 모든 원소 중 가장 크거나 우선순위가 높은 원소가 top 에 오도록 설계되어있다.

내부적으로 heap 의 자료구조를 갖는다.

priority_queue 는 제일 상단의 원소의 확인/삭제 만 가능하다.

priority_queue 에 대한 일반적인 연산의 복잡도는 다음과 같다.

원소의 추가 : O(log N)
우선순위가 가장 높은 원소의 확인 : O(1)
우선순위가 가장 높은 원소의 제거 : O(log N)

multiset 과 비슷하게 동작하지만 사용할 수 있는 기능이 priority_queue 가 더 적다. 반면 속도면에서는 priority_queue 가 더 빠르다.

priority_queue 의 사용

priority_queue 헤더파일

#include <queue>

priority_queue 의 선언

std::priority_queue<Type> Priority_QueueName;
std::priority_queue<Type, std::vector<Type>, std::greater<Type>> Priority_QueueName; // 우선순위 낮은 순

priority_queue 의 생성자 (편의상 int)

std::priority_queue<int> pq;	비어있는 우선순위 큐 pq를 생성
std::priority_queue<int> pq2(pq1);	우선순위 큐 pq1를 복사하여 우선순위 큐 pq2를 생성

priority_queue 의 멤버 함수

std::priority_queue<int> pq;

pq.push(n)	우선순위 큐에 원소 n 삽입
pq.top()	우선순위 큐의 맨 위 원소를 반환
pq.pop()	우선순위 큐의 맨 위 원소를 제거
pq.size()	원소의 개수를 반환
pq.empty()	우선순위 큐 pq가 비어있으면 `true`를 반환
pq2.swap(q1)	pq1 우선순위 큐와 pq2 우선순위 큐를 서로 바꿈

priority_queue 의 원소 삽입/삭제

#include <iostream>
#include <vector>
#include <queue>

int main() 
{
	std::vector<int> v = { 2, 1, 3, 5, 4 };
	std::priority_queue<int> pq;
	
	for (int num : v)
	{
		pq.push(num);
		std::cout << pq.top() << std::endl;
	}

	std::cout << std::endl;
	while(!pq.empty())
	{
		std::cout << pq.top() << std::endl;
		pq.pop();
	}

	return 0;
}