파이썬 우선순위 큐

파이썬에서는 우선순위 큐를 사용할 때 heapq 라이브러리를 이용한다

heapq 자체는 최소 힙을 기반으로 구현돼 있다

따라서 -5 같은 음수 값으로 힙을 구성하면 최대 힙처럼 만들 수도 있다

 

다음과 같은 함수가 제공된다

 

heapq.heappush(heap, item)

힙 불변성을 유지하면서, item 값을 heap으로 푸시한다

 

heapq.heappop(heap)

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환한다

힙이 비어 있으면, IndexError가 발생한다

팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용한다

 

heapq.heapify(x)

리스트 x를 선형 시간으로 힙으로 변환한다

 

import heapq
 
 
heap = []
 
heapq.heappush(heap, -5)
 
heapq.heappush(heap, 5)
 
print(-heapq.heappop(heap))
 
print(heapq.heappop(heap))