우선 순위 큐 (C++ STL의 priority queue)

우선 순위 큐?

우선 순위 큐는 자료구조 중 하나로, 데이터를 우선순위에 따라 정렬하여 관리하는 자료구조입니다.

우선 순위 큐의 구현 방법

우선 순위 큐는 다양한 방법으로 구현될 수 있습니다. 가장 일반적인 구현 방법은 배열을 이용한 구현과 힙을 이용한 구현입니다. 배열을 이용한 구현은 간단하지만, 삽입이나 삭제가 일어날 때마다 정렬해야하므로 시간 복잡도가 높아지는 단점이 있습니다. 반면, 힙을 이용한 구현은 삽입과 삭제가 간단하며, 시간 복잡도가 O(log N)으로 유지됩니다.

우선 순위 큐의 구조

힙으로 구현된 우선 순위 큐

우선 순위 큐는 보통 힙(Heap) 자료구조를 활용하여 구현됩니다. 힙은 이진트리의 일종으로, 최대값 또는 최소값을 빠르게 찾아내기 위해 사용됩니다. 힙은 다음과 같은 특징을 가집니다.

• 완전 이진 트리(Complete Binary Tree)이다.
• 부모 노드는 항상 자식 노드보다 크거나 작다. (최대 힙, 최소 힙)
• 삽입시에는 항상 왼쪽 자식부터 채워나간다.

따라서 우선 순위 큐를 구현할 때에도 힙을 사용하여 데이터를 정렬합니다.

C++ STL의 priority queue

C++ STL에서는 우선 순위 큐를 구현한 priority_queue 클래스가 제공됩니다. 이 클래스는 일반적으로 힙을 기반으로 구현되며, 우선순위에 따라 데이터를 자동으로 정렬해줍니다. 우선순위 큐를 사용하기 위해서는 <queue> 헤더 파일을 포함시켜야 합니다.

Max Heap Priority Queue (default scheme)  & Min Heap Priority Queue

선언 및 초기화

#include <queue>

using namespace std;

// 우선순위 큐 선언
priority_queue<int> pq;

위와 같이 선언하면 pq라는 이름의 우선순위 큐가 생성됩니다. 기본적으로 이 클래스는 내림차순으로 정렬됩니다. 만약 오름차순으로 정렬하고 싶다면, 다음과 같이 작성하면 됩니다.

priority_queue<int, vector<int>, greater<int>> pq;

삽입과 삭제

우선순위 큐에 데이터를 삽입하고 삭제하는 방법은 다음과 같습니다.

// 데이터 삽입
pq.push(3);
pq.push(1);
pq.push(4);

// 데이터 삭제
while(!pq.empty()){
    cout << pq.top() << " ";
    pq.pop();
}

위 코드는 push() 함수로 우선순위 큐에 3, 1, 4를 삽입한 후, top() 함수와 pop() 함수를 사용하여 큐에서 데이터를 삭제하면서 출력하는 코드입니다. 이 코드를 실행하면 4 3 1 순서로 출력됩니다.

우선 순위 힙 데이터 삽입 원리

우선 순위 힙 데이터 삭제 원리

활용 예시

우선순위 큐를 활용하여 다음과 같은 문제를 해결할 수 있습니다.

최대/최소값 구하기

int arr[] = {3, 1, 4, 2, 5};
priority_queue<int> pq(arr, arr + 5);

cout << pq.top();    // 5

위 코드는 배열 arr을 이용하여 우선순위 큐를 생성하고, top() 함수를 사용하여 최대값 5를 출력하는 코드입니다.

K번째로 작은 원소 구하기

int arr[] = {3, 1, 4, 2, 5};
priority_queue<int> pq;

int k = 3;
for(int i = 0; i < 5; i++){
    pq.push(arr[i]);
    if(pq.size() > k) pq.pop();
}

cout << pq.top();    // 3

위 코드는 배열 arr의 K번째로 작은 원소를 구하는 코드입니다. push() 함수로 데이터를 삽입하면서, pop() 함수로 큐의 크기를 K로 유지합니다. 이렇게 하면 마지막에 남는 원소가 K번째로 작은 원소가 됩니다.

우선순위 큐의 멤버 함수

priority_queue 클래스는 다음과 같은 멤버 함수를 제공합니다.

push()	우선순위 큐에 데이터를 삽입합니다.	O(log N)
pop()	우선순위 큐에서 최상위 데이터를 삭제합니다.	O(log N)
top()	우선순위 큐에서 최상위 데이터를 반환합니다.	O(1)
empty()	우선순위 큐가 비어있는지 여부를 반환합니다.	O(1)
size()	우선순위 큐의 크기를 반환합니다.	O(1)

priority_queue 클래스의 시간 복잡도는 대체로 O(log N)입니다. 따라서 큐의 크기가 N인 경우, 삽입, 삭제, 최상위 데이터 반환 등의 연산에 소요되는 시간은 대략 log N 정도가 됩니다. priority_queue의 공간 복잡도는 큐의 크기에 비례합니다.

참고 자료

• GeeksforGeeks: Priority Queue in STL
• cplusplus.com: Priority queue
• 나무위키: 힙
• TechDelight: Introduction to Priority Queues using Binary Heaps