Python heapq 모듈

• heapq 모듈을 사용하여 list를 heap처럼 사용할 수 있음
• 새로운 데이터가 추가되어도 항상 정렬 상태를 유지해야 하는 상황 또는 이미 정렬되어 있는 리스트에 새 원소를 추가하는 경우에 사용함
• python의 heapq 모듈을 사용하여 기본적으로 최소 힙을 구현할 수 있음
• 삽입, 제거의 시간복잡도는 O(logN)

최소 힙

import heapq

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 3)
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

for _ in range(5):
	print(heapq.heappop(heap))

• 위의 코드를 실행하면, 작은 값부터 출력됨을 확인할 수 있음

최대 힙

import heapq

heap = []
heapq.heappush(heap, -4)
heapq.heappush(heap, -3)
heapq.heappush(heap, -5)
heapq.heappush(heap, -1)
heapq.heappush(heap, -2)

for _ in range(5):
	print(-heapq.heappop(heap))

• 위의 코드를 실행하면, 큰 값부터 출력됨을 확인할 수 있음