📌힙(Heap)이란?
최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조이다.
heapq 모듈은 이진트리 기반의 최소 힙 자료구조를 제공한다.
💡 최대 힙 (max heap)
각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙
- heapq 모듈은 최소 힙 기능만을 동작하기 때문에 최대 힙으로 사용하려면 약간 변형해야 한다.
- 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다.
- y = -x 변환을 하면 최소값 정렬이 최대값 정렬로 바뀐다. 힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다. 이때 원소 값의 부호를 바꿨기 때문에 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하는 것이다.
heap = [1,3,5,7,9]
max_heap = []
for h in heap:
heapq.heappush(max_heap, (-h, h))
print(max_heap)💡 최소 힙 (min heap)
각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙
- min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제된다.
- 가장 작은 값은 언제나 인덱스 0 즉, 이진트리의 루트에 위치한다.
- min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2)보다 크기가 작거나 같도록 원소가 추가되고 삭제된다.
heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]import heapq
# heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 해줌
# heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙
heap1 = []
# 힙에 원소 추가
heapq.heappush(heap1, 4)
heapq.heappush(heap1, 1)
heapq.heappush(heap1, 7)
heapq.heappush(heap1, 3)
print(heap) # [1, 3, 7, 4]
# 힙에서 원소 삭제
print(heapq.heappop(heap)) # 1
print(heap) # [3, 4, 7]
heap2 = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap) # 리스트를 힙으로 만드는 함수 heapq.heapify()