[자료구조] 우선순위 큐 (Priority Queue)

우선순위 큐(Priority Queue)

---

우선순위 큐는 큐와 비슷하지만 FIFO방식이 아닌 우선순위를 기준으로 졍렬된 순서대로 요소가 처리되는 자료구조이다. 여기에서 우선순위는 오름차순/ 내림차순/ 사용자 정의 비교연산을 의미한다. 삽입할 때 마다 우선순위대로 정렬할 수도 있고, 정렬하지 않고 차례대로 삽입하여 출력할 때 가장 우선순위가 높은 원소를 찾는 방식으로도 구현될 수 있다. 배열, 리스트, 힙 기반으로 큐를 구현할 수 있지만 일반적인 효율적 구현은 삽입할때 heapify해서 힙 속성을 유지하는 방식이다. 때문에 우선순위큐를 이해하기 위해서는 힙 구조에 대해 먼저 알아야 한다. STL에서는 vector기반의 힙 구조 컨테이너 어댑터 std::priority_queue를 제공한다.

멤버함수	설명	시간복잡도
push(const T& value)	원소 삽입, 힙 속성 유지(heapify)	O(log2 n)
emplace(Args&&... args)	생성자 인자를 사용해 원소 삽입	O(log2 n)
pop()	최고 우선순위 원소 제거	O(log2 n)
top() const	최고 우선순위 원소 조회	O(1)
empty() const	큐가 비어있는지 확인	O(1)
size() const	큐에 들어있는 원소 개수 반환	O(1)

 

 

우선순위큐는 내부적으로 어떤 컨테이너를 사용해야하는가?

 

우선순위큐는 내부적으로 Random Access Iterator(임의 접근 반복자)를 지원하는 컨테이너를 요구한다. std::priority_queue는 vector 컨테이너로 데이터를 관리하는데 vector는 동적 배열이기 때문에 연속된 메모리를 사용해 랜덤 액세스가 가능하다. 우선순위큐의 내부 컨테이너로 list같은 순차 접근만 가능한 컨테이너는 사용이 불가능하다.

 

그 이유는, 우선순위큐는 힙(Heap) 기반으로 구현되는데, 힙 구조 연산을 위해서 배열 기반 인덱스를 통한 부모/ 자식 노드 접근이 필요하기 때문이다. 힙 구조에서 i번째 노드의 부모와 자식 노드의 index를 구할때 index를 통한 연산이 요구되는데, 이러한 연산은 랜덤 액세스가 가능해야 빠르게 접근 가능하고 O(log n)의 시간 복잡도를 유지할 수 있기 때문이다. 만약 순차 접근만 가능한 리스트같은 컨테이너를 사용한다면 i번째 원소에 접근하기 위해 O(n)의 시간이 걸릴 것이다.

 

사용 컨테이너	삽입	삭제
정렬 되지 않은 배열	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬 되지 않은 연결리스트	O(1)	O(n)
정렬된 연결리스트	O(n)	O(1)
힙	O(log2 n)	O(log2 n)

 

 

우선순위큐 기본 코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq; // 기본은 최대 힙 (Max Heap)

    pq.push(10);
    pq.push(30);
    pq.push(20);

    cout << "Top (최대값): " << pq.top() << endl; // 30

    pq.pop();
    cout << "Top after pop: " << pq.top() << endl; // 20

    return 0;
}

 

 

최대 힙(Max Heap)과 최소 힙(Min Heap)

 

우선 순위 큐를 생성하면 디폴트로 최대힙이 만들어진다. 최대힙은 값이 큰 것이 우선순위가 높다고 판단하는 힙으로 top()의 반환값은 최대값이다. 최소힙은 반대로 값이 작은 것이 우선순위가 높다고 판단하는 힙으로 top()의 반환값은 최소값이 된다. 우선순위큐를 최소힙으로 만드려면 greater 함수객체를 comparator로 넘겨주면 된다. 만약 우선순위큐의 데이터 자료형을 사용자 정의 객체로 넣을 경우 비교연산을 하는 함수객체를 만들어 comparator로 넘겨주어야 우선순위를 판단하여 정렬할 수 있다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> minPQ; // 최소 힙

    minPQ.push(10);
    minPQ.push(30);
    minPQ.push(20);

    cout << "Top (최소값): " << minPQ.top() << endl; // 10

    minPQ.pop();
    cout << "Top after pop: " << minPQ.top() << endl; // 20

    return 0;
}

 

 

 

 

 

---

[자료구조] 힙(Heap)