> [!abstract] Introduction > 우선순위 큐(*Priority Queue*)는 각 원소에 우선순위가 부여되어, 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 꺼내는 추상 자료형(*ADT*)입니다. [[Queue]]가 "먼저 들어온 것이 먼저 나가는(FIFO)" 정책을 따르는 것과 달리, 우선순위 큐는 "우선순위가 가장 높은 것이 먼저 나가는" 정책을 따릅니다. 이 글에서는 우선순위 큐의 핵심 연산, 다양한 구현 방법과 시간 복잡도 비교, 이진 힙과의 관계, 그리고 Python `heapq` 모듈을 살펴봅니다. ## 핵심 연산 우선순위 큐는 최소한 다음 세 가지 연산을 지원해야 한다. ![[priorityQueueConcept.svg]] `insert(key, value)` — 새 원소를 우선순위 큐에 삽입한다. `key`가 우선순위를 결정한다. `extract-min()` (또는 `extract-max()`) — 우선순위가 가장 높은 원소를 꺼내서 반환한다. 최소 우선순위 큐(*min-priority queue*)에서는 키가 가장 작은 원소가, 최대 우선순위 큐(*max-priority queue*)에서는 키가 가장 큰 원소가 나온다. `peek()` — 가장 우선순위가 높은 원소를 꺼내지 않고 확인만 한다. 이 외에도 `decrease-key()`[^decrease-key]는 이미 큐 안에 있는 원소의 키를 더 작은 값으로 갱신하는 연산으로, Dijkstra 알고리즘과 Prim의 최소 신장 트리 알고리즘에서 핵심적으로 쓰인다. ## 구현 방법과 시간 복잡도 우선순위 큐는 **추상 자료형**이므로 여러 가지 방법으로 구현할 수 있다. 어떤 구현을 선택하느냐에 따라 각 연산의 시간 복잡도가 달라진다. | 구현 | `insert` | `extract-min` | `decrease-key` | |------|----------|---------------|----------------| | 비정렬 배열 | $O(1)$ | $O(n)$ | $O(1)$ | | 정렬 배열 | $O(n)$ | $O(1)$ | $O(n)$ | | **이진 힙** | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | | 피보나치 힙 | $O(1)$* | $O(\log n)$* | $O(1)$* | \* 상각 시간 복잡도(*amortized*) 비정렬 배열은 삽입이 $O(1)$이지만 최솟값을 찾으려면 전체를 순회해야 한다. 정렬 배열은 반대로 꺼내기는 빠르지만 삽입 시 정렬을 유지해야 한다. **이진 힙**은 모든 연산이 $O(\log n)$으로 균형 잡혀 있어 실무에서 가장 널리 쓰인다. ## 이진 힙과의 관계 우선순위 큐의 가장 대표적인 구현이 [[Heap]](이진 힙)이다. 이진 힙은 **완전 이진 트리**[^complete-binary-tree] 구조를 1차원 배열로 표현한 것으로, 부모-자식 관계를 인덱스 연산으로 처리한다. 인덱스가 $i$인 노드의 부모는 $\lfloor i/2 \rfloor$, 왼쪽 자식은 $2i$, 오른쪽 자식은 $2i + 1$이다 (1-based 인덱스 기준). **최소 힙 속성**(*min-heap property*): 모든 노드의 키가 자식 노드의 키보다 작거나 같다. 이 속성 덕분에 루트가 항상 최솟값이므로 `peek()`이 $O(1)$이다. 삽입 시에는 배열 끝에 원소를 추가한 뒤, 부모와 비교하며 위로 올리는 **sift-up** 연산을 수행한다. 추출 시에는 루트를 꺼내고 마지막 원소를 루트에 놓은 뒤, 자식과 비교하며 아래로 내리는 **sift-down** 연산을 수행한다. 두 연산 모두 트리의 높이인 $O(\log n)$에 완료된다. ## Python `heapq` 모듈 Python 표준 라이브러리의 `heapq` 모듈은 최소 힙 기반의 우선순위 큐를 제공한다. 별도의 클래스가 아닌 일반 리스트 위에서 동작하며, 다음과 같이 사용한다. ```python import heapq pq = [] # 빈 리스트 = 빈 힙 heapq.heappush(pq, (3, "low")) # (우선순위, 값) 삽입 heapq.heappush(pq, (1, "high")) heapq.heappush(pq, (2, "mid")) print(heapq.heappop(pq)) # (1, 'high') — 가장 작은 키 print(heapq.heappop(pq)) # (2, 'mid') print(heapq.heappop(pq)) # (3, 'low') ``` 튜플의 첫 번째 원소가 우선순위(키)로 사용되며, 값이 같을 때 두 번째 원소로 비교한다. 탐색 알고리즘에서는 보통 `(f값, 삽입순서, 노드)` 형태의 3-튜플을 사용하여 f값이 동일할 때 삽입 순서로 타이브레이킹한다. `heapq`는 `decrease-key`를 직접 지원하지 않는다. 대신 "lazy deletion" 기법을 사용한다 — 기존 항목을 삭제하지 않고 새 키로 다시 삽입한 뒤, 꺼낼 때 이미 처리된 항목인지 확인하여 무시한다. [[A*]]의 Python 구현에서 `closed` 집합을 검사하는 것이 바로 이 기법이다. ## 어디에 쓰이는가 우선순위 큐는 "가장 좋은 것을 먼저 처리하라"는 패턴이 필요한 곳이면 어디든 쓰인다. 대표적으로 Dijkstra 알고리즘과 [[Uniform-Cost Search]]에서 비용이 가장 적은 노드를 먼저 확장하는 데 사용하고, [[A*]]에서 $f(n) = g(n) + h(n)$이 가장 작은 노드를 꺼내는 데 사용한다. 운영체제의 프로세스 [[Scheduler]]에서도 우선순위가 높은 프로세스를 먼저 실행하기 위해 우선순위 큐를 활용한다. --- ## 출처 - Cormen, T. H. et al. (2022) *Introduction to Algorithms*. 4th edn. Cambridge, MA: MIT Press. Chapter 6.5. - Python Software Foundation (2025) *heapq — Heap queue algorithm*. Available at: https://docs.python.org/3/library/heapq.html. [^decrease-key]: `decrease-key` — 이미 큐 안에 있는 원소의 우선순위(키)를 더 작은 값으로 변경하는 연산. 이진 힙에서는 키를 갱신한 뒤 sift-up을 수행하여 $O(\log n)$에 처리한다. [^complete-binary-tree]: 완전 이진 트리(*complete binary tree*) — 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진 이진 트리. 배열로 표현하기에 최적의 구조다.