pythonでpriority_queue（優先度付きキュー）を使う
pythonでpriority_queueを使います。
pythonではheapqとして実装されていますので、使用する場合はheapqをインポートします。
import heapq
さて、heapqを使用するメリットですが、大きく2つ、
- 最小値をO(logN)で取得する
- 要素をO(logN)で挿入する
があります。
以下、簡単な使い方です。
heapqの生成
#リストをheapqへ a = [1,2,3,5,-1,0,9,12] heapq.heapify(a)
要素の挿入
heapq.heappush(a, -5)
要素の取得
heapq.heappop(a)
最後に、heapqを使用した問題を紹介します。
