[파이썬][중급] Chapter16. heapq와 우선순위 큐

우선순위 큐(Priority Queue)는 가장 높은(또는 낮은) 우선순위를 가진 요소를 빠르게 꺼낼 수 있는 자료 구조입니다. 파이썬에서는 heapq 모듈을 통해 최소 힙(min-heap) 기반의 우선순위 큐를 효율적으로 구현할 수 있습니다.

● heapq란?

heapq는 힙(heap) 알고리즘을 기반으로 하는 우선순위 큐 모듈입니다. 리스트를 힙으로 다룰 수 있도록 해주며, 시간 복잡도 O(log n)으로 요소를 삽입하거나 꺼낼 수 있습니다.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heapq.heappop(heap))  # 1

위 코드에서 가장 작은 값인 1이 먼저 추출됩니다. heap은 자동으로 힙 속성을 유지합니다.

● 리스트를 힙으로 변환

기존 리스트를 힙 구조로 변환하려면 heapify()를 사용합니다.

nums = [4, 2, 7, 1]
heapq.heapify(nums)
print(heapq.heappop(nums))  # 1

heapify는 in-place로 작동하므로 별도의 리스트 생성 없이 정렬 구조를 유지할 수 있습니다.

● 최대 힙 구현

heapq는 기본적으로 최소 힙만 지원하므로, 최대 힙은 음수 값을 활용하여 구현합니다.

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -1)
print(-heapq.heappop(max_heap))  # 10

● 튜플을 이용한 우선순위 설정

튜플의 첫 번째 요소를 기준으로 자동 정렬되므로, 우선순위 큐를 구현할 때 자주 사용됩니다.

tasks = []
heapq.heappush(tasks, (2, "코딩"))
heapq.heappush(tasks, (1, "과제"))
print(heapq.heappop(tasks))  # (1, '과제')

● 마무리

heapq는 빠르고 간결하게 우선순위 큐를 구현할 수 있는 훌륭한 도구입니다. 알고리즘 문제 풀이, 작업 스케줄링, 이벤트 처리 등에서 매우 유용하므로 꼭 숙지해두시기 바랍니다.