[STL] 14. std::priority_queue

std::priority_queue는 C++ 표준 라이브러리(STL)에서 제공하는 우선순위 큐를 구현한 컨테이너 어댑터이며,

내부적으로 힙(Heap) 자료구조를 사용하여 구현되어 있고 <queue> 헤더 파일에 정의되어 있다.

우선순위 큐는 각 요소가 우선순위를 가지며, 가장 높은 우선순위를 가진 요소가 가장 먼저 나오는 특성이 있다.

그리고 std::priority_queue는 std::queue와 유사하지만, 요소들이 큐에 들어갈 때마다 자동으로 정렬되어

우선순위가 높은 요소가 먼저 나오게 되며, 기본적으로 최대 힙(Max Heap)이 사용되어 요소들이 내림차순으로 정렬된다.

즉, 가장 큰 요소가 가장 앞에 위치한다는 말이다.

 

 

특징

 

1. 힙 기반 구현 : 내부적으로 이진 힙(Binary Heap) 자료구조를 사용하여 구현되어 있으며,

새로운 원소를 삽입하거나 최상위 원소를 제거할 때마다 특정 규칙에 따라 재배열되어 우선순위 큐의 특성을 유지한다.

2. 기본 정렬 순서 : 기본적으로 내림차순으로 정렬된 최대 힙(Max Heap)을 사용한다.

3. 사용자 정의 정렬 : std::priority_queue를 선언할 때 비교 함수나 비교자를 제공해 원하는 정렬 순서를 지정할 수 있다.

4. 삽입 및 삭제 연산 : push()를 사용해 원소를 삽입하고, pop()을 사용해 우선순위가 높은 원소를 제거한다.

이러한 연산들은 힙의 특성에 따라 O(log n)의 시간 복잡도를 가진다.

5. 상위 원소에 빠른 접근 : top()을 사용하여 우선순위가 높은(혹은 낮은, 최소 힙의 경우) 원소에 빠르게 접근할 수 있다.

6. 특정 위치의 원소에 직접 접근 불가 : 힙은 완전 이진 트리의 형태를 가지기 때문에

특정 위치의 원소에 직접 접근하는 것은 불가능하다.

 

 

사용법

 

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

template<typename T>
void print_queue(T q) {

	while (!q.empty()) {

		std::cout << q.top() << ", ";
		q.pop();
	}

	std::cout << std::endl;
}

int main() {

	std::vector<int> vec { 4,2,3,5,1 };

	std::priority_queue<int> pq1;

	for (auto n : vec) {

		pq1.push(n);
	}
	
	print_queue(pq1);

	//오름차순
	std::priority_queue<int, std::vector<int>, std::greater<>> pq2(vec.begin(), vec.end());

	print_queue(pq2);
}

 

 

주요 멤버 함수와 기능

 

멤버 함수	설명	시간 복잡도
push()	요소를 우선순위 큐에 추가한다.	O(log n)
pop()	우선순위가 높은 요소를 제거한다.	O(log n)
top()	우선순위가 높은 요소에 접근한다.	O(1)
size()	현재 우선순위 큐의 요소 개수를 반환한다.	O(1)
empty()	우선순위 큐가 비어있는지 여부를 확인한다.	O(1)