Pythonでの優先度付きキューはheapqを使うとできます。
import heapq
最小ヒープ
はじめに、リストをキューに優先度付きキューに変換します。
que = [3, 1, 5, 2] heapq.heapify(que)
先頭に最小値がきます。(先頭以外はソートされているわけではありません。)
print(que) # [1, 2, 5, 3]
要素を追加します。(計算量: O(logN)
)
heapq.heappush(que, 4) print(que) # [1, 2, 5, 3, 4] heapq.heappush(que, -1) print(que) # [-1, 1, 2, 5, 3, 4]
要素を取り出します。(計算量: O(1)
)
v = heapq.heappop(que) print(v) # -1
最大ヒープ
heapq
では最小ヒープですが、最大ヒープを利用したい場合は、デフォルトではないので-1
をかける必要があります。
que = [4, 5, 9, 7] que = [x * -1 for x in que] heapq.heapify(que) print(que) # [-9, -7, -4, -5]
heapq.heappush(que, 2 * -1) print(que) # [-9, -7, -4, -5, -2] v = heapq.heappop(que) * -1 print(v) # 9