【Python】heapq

Pythonのheap queueアルゴリズム
完全なバイナリツリーはheaq実装,heaqは配列(リスト)実装を用いる.
したがってheapの作成時には[]に初期化されたlistを使用します.
heapqの使用
Pythonにはheapqという内蔵モジュールがあります.このheapqを使用して優先キューを実装できます.PriorityQueueというモジュールも存在し、heapqはパフォーマンスの面でずっと優れています.
Pythonでheapqを使用するには、次のような内容をインポートする必要があります.

import heapq

heapqの作成
hipは配列を利用して実現されるので,最小hipを作成するには配列を初期化する.

import heapq

queue = []

heapq push
heapq.heappush(heap, item)
お尻を押すにはheapqモジュールのheappushという関数を使用する必要があります.

import heapq

queue = []

heapq.heappush(queue, 1)
heapq.heappush(queue, 2)
heapq.heappush(queue, -3)

heapq pop
heapq.heappop(heap)
pop hipの最小要素を使用する場合は、heapqモジュールのheapppopという関数を使用する必要があります.

import heapq

queue = []

heapq.heappush(queue, 1)
heapq.heappush(queue, 2)
heapq.heappush(queue, -3)

element = heapq.heappop(queue) # -3

heapq pushそれから直接pop
heapq.heappushpop(heap, item)
お尻から押すとポップが踊れる関数もあります.heappush+heapppopよりも効率的です.

import heapq

queue = []

heapq.heappush(queue, 1)
heapq.heappush(queue, 2)
heapq.heappush(queue, -3)

element = heapq.heappushpop(queue, -4) # -4 

heapq[]を直接heapに変換
heapq.heapify(list)
listxをheapに変換します.この場合はリニアタイムが必要です.

import heapq

queue = [-4, 1, 2, -3]

heapq.heapify(queue)

アルゴリズムの問題を解くときのヒント
お尻に入った要素をすべて外に置くと、whileheapと呼ばれると取り出しやすいです.

import heapq

queue = []

heapq.heappush(queue, 1)
heapq.heappush(queue, 2)
heapq.heappush(queue, -3)
heapq.heappush(queue, -4)

while queue:
	element = heapq.heappop(queue)
    print(element)

# 결과 (가장 작은 값부터 pop되는 것을 볼 수 있다.)
# -4
# -3
# 1
# 2

注意:https://docs.python.org/3/library/heapq.html