우선순위 큐는 값이 들어오고 나가는 중에도 가장 우선순위가 높은 값을 빠르게 꺼내기 위한 자료구조입니다. 정렬과 비슷해 보이지만, 핵심은 전체를 한 번 정렬하는 것이 아니라 매 순간 필요한 최솟값이나 최댓값을 꺼내는 것입니다.
힙은 우선순위 큐를 구현하는 대표 방식입니다. Python의 heapq와 Java의 PriorityQueue는 모두 이 흐름을 이해하면 훨씬 자연스럽게 쓸 수 있습니다.
정렬로 충분한 상황
모든 데이터가 이미 주어져 있고, 한 번 정렬한 뒤 순서대로 쓰면 되는 문제라면 정렬이 단순합니다. 예를 들어 점수 목록을 내림차순으로 출력하는 문제는 정렬이 자연스럽습니다.
scores = [80, 95, 70, 100]
scores.sort(reverse=True)
print(scores[0]) # 가장 큰 점수하지만 데이터가 계속 추가되고, 중간중간 가장 작은 값이나 큰 값을 꺼내야 한다면 매번 정렬하는 방식은 비효율적입니다.
우선순위 큐가 필요한 신호
- 값이 계속 추가된다
- 중간중간 최솟값 또는 최댓값을 꺼내야 한다
- 전체 정렬 결과보다 현재 가장 우선순위 높은 값 하나가 중요하다
- 스케줄링, Top K, 최단거리처럼 동적으로 후보가 바뀐다
이런 문제에서는 정렬된 전체 목록을 유지하려 하기보다 heap에 넣고 필요할 때 pop하는 흐름이 더 잘 맞습니다.
Python heapq 기본 사용법
Python heapq는 기본적으로 min heap입니다. 가장 작은 값이 먼저 나옵니다.
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
print(heapq.heappop(heap)) # 2
print(heapq.heappop(heap)) # 5최댓값이 필요하면 보통 값을 음수로 넣어 max heap처럼 씁니다.
heapq.heappush(heap, -score)
max_score = -heapq.heappop(heap)Java PriorityQueue 기본 사용법
Java의 PriorityQueue도 기본은 작은 값이 먼저 나오는 구조입니다. 객체를 넣을 때는 Comparator로 우선순위를 정할 수 있습니다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(8);
System.out.println(pq.poll()); // 2PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Comparator.reverseOrder());시간복잡도 감각
- 삽입 push/offer: 보통 O(log n)
- 삭제 pop/poll: 보통 O(log n)
- 최솟값 확인 peek: 보통 O(1)
- 전체 정렬: 보통 O(n log n)
값 하나가 들어올 때마다 전체를 다시 정렬하면 비용이 커집니다. 우선순위 큐는 필요한 위치만 조정해 최솟값 구조를 유지합니다.
Top K 문제에서 왜 유용할까
큰 데이터에서 상위 k개만 필요할 때 전체를 모두 정렬할 필요가 없습니다. 크기 k인 min heap을 유지하면 현재 top k 후보만 관리할 수 있습니다.
import heapq
def top_k(nums: list[int], k: int) -> list[int]:
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return sorted(heap, reverse=True)다익스트라에서의 우선순위 큐
다익스트라는 아직 확정되지 않은 정점 중 현재 거리가 가장 짧은 정점을 계속 꺼내야 합니다. 이 후보는 간선을 따라가며 계속 바뀌기 때문에 우선순위 큐가 잘 맞습니다.
heap = [(0, start)]
while heap:
dist, node = heapq.heappop(heap)
if dist > distance[node]:
continue
for next_node, cost in graph[node]:
next_dist = dist + cost
if next_dist < distance[next_node]:
distance[next_node] = next_dist
heapq.heappush(heap, (next_dist, next_node))여기서 heap에는 같은 노드가 여러 번 들어갈 수 있습니다. 대신 꺼낼 때 이미 더 좋은 거리가 기록되어 있으면 건너뛰는 방식으로 처리합니다.
자주 하는 실수
- PriorityQueue를 쓰면 내부 배열이 완전히 정렬되어 있다고 착각한다
- Python heapq에서 최댓값이 필요한데 음수 변환을 빼먹는다
- Java 객체 정렬 기준을 Comparator로 명확히 주지 않는다
- heap 안의 특정 원소를 중간에서 삭제하려고 한다
- 모든 값의 최종 정렬이 필요한 문제에 heap을 억지로 쓴다
정리
우선순위 큐는 전체를 정렬하기 위한 자료구조가 아니라, 계속 변하는 후보 중 가장 우선순위 높은 값을 빠르게 꺼내기 위한 도구입니다.
Python 구현은 heapq 문서, Java 구현은 PriorityQueue 문서에서 확인할 수 있습니다. 그래프 흐름은 그래프 입력 글과 함께 보면 좋습니다.
