[Python] heapq 모듈 사용법

heap

•  2021.10.03 - [ALGORITHM/개념 정리] - [Algorithm] 힙 (Heap)
• python에서는 heapq 모듈을 사용하여 리스트를 최소 힙처럼 사용 가능
• heapq를 사용하여 만든 최소 힙의 0번째 인덱스는 항상 최소 값

 

heap = []

 

[원소 추가]

• heappush() : 내부적으로 이진 트리에 원소 추가, O(logN)

heapq.heappush(heap, 1)

 

[원소 삭제]

• heappop() : 가장 작은 원소를 삭제한 후 삭제한 값 리턴, O(logN)

heapq.heappop(heap)

 

[기존 리스트 힙으로 변환]

heapq.heapify(heap)