heapq

• 우선순위 큐 알고리즘이라고도 하는 힙 큐 알고리즘이다.
• 최소 힙(min heap)을 기본으로 하기 때문에 리스트의 맨 앞은 가장 작은 값이 들어가 있다.

사용법

import heapq

heap = []
xlist = [3, 5, 1, 2]
heapq.heappush(heap, item) # item 값을 heap으로 푸시한다.
heapq.heappop(heap) # heap에서 가장 작은 항목을 팝하고 반환한다. 
heapq.heappushpop(heap, item) # item을 푸시한 다음, 가장 작은 항목을 팝하고 반환한다.
heapq.heapify(xlist) # xlist를 최소 힙으로 변환한다.

우선순위 큐로 활용하기

• 우선순위 큐로 활용하기 위해서 item자리에 튜플이나 배열로 된 [우선순위, 값]을 대신 넣는다.
• [우선순위, 값]안의 순서가 바뀌면 제대로 동작하지 않으므로 0번 인덱스에 우선순위가 있어야한다.

import heapq

heap = []
heapq.heappush(heap, [4, 'A']) # 튜플도 된다.
heapq.heappush(heap, [1, 'B'])
heapq.heappush(heap, [3, 'C'])