eapq

heapq 우선순위 큐

heapq 모듈은 보통의 리스트를 최소 힙처럼 다룰 수 있게 해준다.
빈 리스트를 생성한 다음, heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 한다.
파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이다.

힙에 원소 추가.

heapq.heappush(list,data)

import heapq

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

print(heap)

# 결과
[1, 3, 5, 10]

힙에서 원소 삭제

heapq.heappop(list)

heapq.heappop(heap)
print(heap)

# 결과
[3, 10, 5]

기존 리스트를 힙으로 변환.

heapq.heapify(list)

arr = [4, 1, 7, 3, 8, 5]
heapq.heapify(arr)
print(arr)

# 결과
[1, 3, 5, 4, 8, 7]

최대 힙 (응용)

arr = [4, 1, 7, 3, 8, 5]
heap = []

for i in arr:
    heapq.heappush(heap, (-i, i))  # 쌍으로 넣기.

# print(heap)
# [(-8, 8), (-7, 7), (-5, 5), (-1, 1), (-3, 3), (-4, 4)]

while heap:
    print(heapq.heappop(heap)[1])

# 결과
8 7 5 4 3 1