파이썬의 heapq 모듈로 힙 자료구조 사용하기
[Python] heap과 heapq 모듈
Python heapq 모듈 사용법
heapq
모듈은 이진 트리 기반의 최소 힙 자료구조를 제공[3, 6, 4, 8, 2, 1]
Tip! 추가 내용
- 힙 속성
- A가 B의 부모 노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립
- 최소 힙 (
Min Heap
)
- 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
- 최대 힙 (
Max Heap
)
- 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙
1
부모 인덱스 * 2
부모 인덱스 * 2 + 1
push
나 pop
을 실행하면 자식 인덱스와 비교하면서 루트까지 오게 됨import heapq
heap = []
heapq.heppush()
함수를 이용heapq.heappush(heap, item)
heapq.heappush(heap, item2)
print(heap)
>>> [item, item2]
[0]
인덱싱을 통해 접근하면 됨heap = [1, 2, 3, 4, 5]
heapq.heapppop(heap)
print(heap)
>>> [2, 3, 4, 5]
arr = [3, 5, 2, 4]
heapq.heapify(arr)
print(arr)
>>> [2, 3, 4, 5]
heapq
에서는 최소 힙만 지원-
로 바꿔줘야 함reverse = lambda x: x * -1
max_heap = list(map(reverse, heap))
heapq.heapify(max_heap)
max_heap = list(map(reverse, max_heap))