우선순위 큐

원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것

heapq 모듈

파이썬의 리스트를 마치 힙처럼 다룰 수 있게 도와준다.

heappush(heap, item)

힙 불변성을 유지하면서, item 값을 heap으로 push 해주는 메소드

heappop(heap)

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 pop하고 반환해주는 메소드

• 힙이 비어 있을 때 heappop 메소드를 호출하면 IndexError가 발생

예시

from heapq import heappush, heappop

heap = []
heappush(heap,3)
heappush(heap,8)
heappush(heap,2)
print(heap)

>>>[2, 8, 3]

heappop(heap)
>>> 2

print(heapq)
>>>[8, 3]

heapify()

원소가 들어있는 리스트를 힙으로 만들어주는 함수

• 새로운 리스트를 반환하는 것이 아니라 인자로 넘긴 리스트에 직접 변경함

from heapq import heapify

heap = [2, 8, 3, 1, 5]
heapify(heap)
print(heap)

>>> [1, 2, 3, 8, 5]