파이썬에서 힙 사용법 핸드북
핵심 요약
파이썬 표준 라이브러리의 heapq 모듈은 최소 힙(min-heap) 구현체를 제공하여, 리스트를 입력받아 최솟값 추출·삽입을 모두 **O(log n)**에 처리할 수 있다. 우선순위 큐, 실시간 중간값 계산, 이벤트 시뮬레이션 등에 활용된다.
1. 기본 준비
import heapq2. 주요 함수 비교
| 함수 | 설명 | 시간 복잡도 |
|---|---|---|
heapq.heapify(x) | 리스트 x를 in-place로 최소 힙 구조로 변환 | O(n) |
heapq.heappush(h,v) | 힙 h에 값 v를 삽입 | O(log n) |
heapq.heappop(h) | 힙 h에서 최솟값을 제거·반환 | O(log n) |
heapq.heappushpop(h,v) | v를 삽입한 뒤 즉시 최솟값을 제거·반환 (push+pop 동시) | O(log n) |
heapq.heapreplace(h,v) | 최솟값 제거 후 v 삽입 (pop+push 동시) | O(log n) |
heapq.nlargest(n,iter) | iterable에서 n개의 최댓값을 리스트로 반환 | O(n + k log n) |
heapq.nsmallest(n,iter) | iterable에서 n개의 최솟값을 리스트로 반환 | O(n + k log n) |
3. 기본 사용 예제
3.1 힙 생성 및 최솟값 조회
import heapq
nums = [10, 20, 15, 30, 40]
heapq.heapify(nums) # [10,20,15,30,40] → 최소 힙으로 재정렬
print(nums[^0]) # 루트(최솟값): 103.2 삽입과 제거
heapq.heappush(nums, 5) # 삽입 후: [5,20,10,30,40,15]
min_val = heapq.heappop(nums) # 최솟값 제거: 5
print(min_val, nums) # 출력: 5 [10,20,15,30,40]3.3 삽입+제거 동시
# 새 값을 넣고 바로 최솟값을 꺼낸다.
min_removed = heapq.heappushpop(nums, 12)
print(min_removed, nums)3.4 대량 최댓값·최솟값
data = [7,1,3,9,5,2]
top3 = heapq.nlargest(3, data) # [9,7,5]
bottom3 = heapq.nsmallest(3, data) # [1,2,3]4. 최대 힙 구현
heapq는 최소 힙만 지원하므로, 값에 - 부호를 적용해 최대 힙처럼 사용할 수 있다.
import heapq
nums = [1,3,5,2,4]
max_heap = [-x for x in nums]
heapq.heapify(max_heap) # 최소 힙이지만 내부값은 음수
largest = -heapq.heappop(max_heap)
print(largest) # 55. 우선순위 큐 예제
import heapq
pq = []
# (우선순위, 태스크) 튜플 삽입
heapq.heappush(pq, (2, 'B'))
heapq.heappush(pq, (1, 'A'))
heapq.heappush(pq, (3, 'C'))
# 우선순위가 가장 작은(높은 우선순위) 작업부터 처리
while pq:
priority, task = heapq.heappop(pq)
print(f'처리 중: {task} (우선순위 {priority})')6. 활용 팁
- 실시간 중간값(Median) 계산: 두 힙(최대 힙 + 최소 힙)을 함께 사용.
- 이벤트 시뮬레이션: 시간순 호출 이벤트 관리.
- 그래프 알고리즘: 다익스트라·프림 알고리즘의 우선순위 큐 구현체.
- 스트리밍 Top-K 문제: 실시간으로 K개의 최댓값/최솟값 유지.
7. 결론
heapq 모듈은 간단한 API로도 강력한 우선순위 큐 기능을 제공하여, 삽입·삭제를 로그 시간에 처리해야 하는 모든 상황에서 유용하다. 최대 힙 구현, nlargest/nsmallest 함수, heappushpop·heapreplace 등의 연산을 숙지하면 다양한 알고리즘과 시스템 설계에 즉시 적용할 수 있다.
⁂