파이썬에서 힙 사용법 핸드북

핵심 요약

파이썬 표준 라이브러리의 heapq 모듈은 최소 힙(min-heap) 구현체를 제공하여, 리스트를 입력받아 최솟값 추출·삽입을 모두 **O(log n)**에 처리할 수 있다. 우선순위 큐, 실시간 중간값 계산, 이벤트 시뮬레이션 등에 활용된다.

1. 기본 준비

import heapq

2. 주요 함수 비교

함수설명시간 복잡도
heapq.heapify(x)리스트 xin-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])                 # 루트(최솟값): 10

3.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)                # 5

5. 우선순위 큐 예제

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 등의 연산을 숙지하면 다양한 알고리즘과 시스템 설계에 즉시 적용할 수 있다.