Nagie's DevStory
[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) |