heapq

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.
모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조인데. 내부적으로는 인덱스 0에서 시작해
k번째 원소가 항상 자식 원소들보다 작거나 같은 최소 힙의 형태로 정렬된다.
heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

heap 함수 활용하기

1.heapq.heappush(heap, item) : item을 heap에 추가
2.heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
3.heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

heap 생성 & 원소 추가

리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야한다

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

->[10,20,30]

heap 원소 삭제

heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결과 값으로 리턴한다

result = heapq.heappop(heap)

print(result)
print(heap)

->10
[20,50]