[Python] heapq 라이브러리

파이썬에는 heapq 라는 라이브러리가 있다.

import heapq

heapq는 파이썬의 내장 모듈로, 힙(heap) 자료구조를 쉽게 사용할 수 있게 해준다.

heapq 라이브러리 사용하면 우선순위 큐(priority queue)도 쉽게 구현할 수 있다.

 

힙(Heap)이란?

힙(Heap)은 완전 이진 트리*의 형태로, 부모 노드가 자식 노드보다 작거나 같은 구조(최소 힙)이다. 

따라서 루트 노드는 항상 최솟값이다.

최소 힙을 사용하면 가장 작은 원소에 빠르게 접근할  수 있다.

힙 구조 예시

부모 노드가 자식 노드보다 크거나 같은 경우(최대 힙)도 있다.

* 완전 이진 트리: 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리

 

heapq 주요 함수

heappush(heap, x)	힙에 원소 x를 추가	heapq.heappush(heap, 5)
heappop(heap)	힙에서 최소 원소를 제거하고 반환	min_val = heapq.heappop(heap)
heapify(x)	리스트 x를 힙 구조로 변환	heapq.heapify(my_list)
heappushpop(heap, x)	원소를 추가하고 최소 원소를 반환	res = heapq.heappushpop(heap, 7)
heapreplace(heap, x)	최소 원소 제거 후 새 원소 추가	heapq.heapreplace(heap, 9)

#최소 힙
import heapq

heap = []

# 원소 추가
heapq.heappush(heap, 20)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)

print(heap)  # 출력: [5, 20, 15] - 내부적으로 최소값이 앞에 옴

# 최소 원소 꺼내기
print(heapq.heappop(heap))  # 출력: 5
print(heapq.heappop(heap))  # 출력: 15
print(heapq.heappop(heap))  # 출력: 20

파이썬 heapq는 최소 힙만 지원한다. 
최대 힙을 구현하려면, 원소를 음수로 변환해서 저장하면 된다.

#최대 힙
import heapq

max_heap = []

heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)

print(-heapq.heappop(max_heap))  # 출력: 20 (가장 큰 값)
print(-heapq.heappop(max_heap))  # 출력: 10
print(-heapq.heappop(max_heap))  # 출력: 5