heapq
힙은 우선순위 큐(priority queue)를 구현하는 데 사용되며, 정렬된 순서를 유지하면서 요소를 빠르게 삽입하고 삭제할 수 있게 해줍니다. 파이썬에서는 heapq 라이브러리를 통해 이러한 힙 구조를 사용할 수 있습니다. heapq 모듈의 기본적인 사용법과 특징에 대해 알아보겠습니다.
힙(Heap)이란?
힙은 완전 이진 트리의 한 형태로, 각 노드가 자식 노드보다 작거나 같은(최소 힙) 또는 크거나 같은(최대 힙) 순서를 가지고 있는 자료 구조입니다. 최소 힙에서는 루트 노드가 항상 가장 작은 값을 가지며, 최대 힙에서는 가장 큰 값을 가집니다.
heapq 모듈 사용하기
파이썬의 heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있게 해줍니다.
- heapify(list): 리스트를 힙으로 변환합니다.
- heappush(heap, item): 힙에 새로운 요소를 추가합니다.
- heappop(heap): 힙에서 가장 작은 요소를 제거하고 반환합니다.
- heapreplace(heap, item): 힙에서 가장 작은 요소를 제거하고 새로운 요소를 추가합니다.
최소 힙 구현
import heapq
# 빈 리스트를 힙으로 초기화
heap = []
heapq.heapify(heap)
# 힙에 요소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
# heap = [1, 3, 4]
# 가장 작은 요소 제거 및 반환
print(heapq.heappop(heap)) # 출력: 1
최대 힙 구현
파이썬 heapq는 기본적으로 최소 힙을 제공하지만, 요소에 음수를 적용함으로써 최대 힙처럼 사용할 수 있습니다.
heap = []
heapq.heappush(heap, -1)
heapq.heappush(heap, -4)
heapq.heappush(heap, -3)
# heap = [-4, -3, -1]
print(-heapq.heappop(heap)) # 출력: 4