Priority Queue

핵심 연산

우선순위 큐는 최소한 다음 세 가지 연산을 지원해야 한다.

insert(key, value) — 새 원소를 우선순위 큐에 삽입한다. key가 우선순위를 결정한다.

extract-min() (또는 extract-max()) — 우선순위가 가장 높은 원소를 꺼내서 반환한다. 최소 우선순위 큐(min-priority queue)에서는 키가 가장 작은 원소가, 최대 우선순위 큐(max-priority queue)에서는 키가 가장 큰 원소가 나온다.

peek() — 가장 우선순위가 높은 원소를 꺼내지 않고 확인만 한다.

이 외에도 decrease-key()¹는 이미 큐 안에 있는 원소의 키를 더 작은 값으로 갱신하는 연산으로, Dijkstra 알고리즘과 Prim의 최소 신장 트리 알고리즘에서 핵심적으로 쓰인다.

구현 방법과 시간 복잡도

우선순위 큐는 추상 자료형이므로 여러 가지 방법으로 구현할 수 있다. 어떤 구현을 선택하느냐에 따라 각 연산의 시간 복잡도가 달라진다.

* 상각 시간 복잡도(amortized)

비정렬 배열은 삽입이 $O(1)$이지만 최솟값을 찾으려면 전체를 순회해야 한다. 정렬 배열은 반대로 꺼내기는 빠르지만 삽입 시 정렬을 유지해야 한다. 이진 힙은 모든 연산이 $O(\log n)$으로 균형 잡혀 있어 실무에서 가장 널리 쓰인다.

이진 힙과의 관계

우선순위 큐의 가장 대표적인 구현이 Heap(이진 힙)이다. 이진 힙은 완전 이진 트리² 구조를 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 모듈은 최소 힙 기반의 우선순위 큐를 제공한다. 별도의 클래스가 아닌 일반 리스트 위에서 동작하며, 다음과 같이 사용한다.

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.

Footnotes

1. decrease-key — 이미 큐 안에 있는 원소의 우선순위(키)를 더 작은 값으로 변경하는 연산. 이진 힙에서는 키를 갱신한 뒤 sift-up을 수행하여 $O(\log n)$에 처리한다. ↩

2. 완전 이진 트리(complete binary tree) — 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진 이진 트리. 배열로 표현하기에 최적의 구조다. ↩