～ 優先度付きキュー ～ チートシート

#目次
まずは使用するライブラリをインポート import heapq

リストを優先度付きキューに変換　heapq.heapify(mat)
優先度付きキューから最小値を取り出す　heapq.heappop(mat)
要素を優先度付きキューに追加　heapq.heappush(mat, num)

最大値を扱う場合

#はじめに

チートシートの扱いついてはここを読んでください

#リストを優先度付きキューに変換

queue.py

import heapq

mat = [1, 1, 4, 5, 1, 4]

heapq.heapify(mat)
print(mat)

mat

>>> [1, 1, 4, 5, 1, 4]

優先度付きキュー（二分木）はソートされた配列とは異なるが、最も優先度の高い要素（配列の1つ目の要素）が配列内で最小となる
配列の最小値を頻繁に求める場合、ソートよりも計算量を落とすことが可能
リストを優先度付きキューに変換するには、最初に heapq.heapify() する

#優先度付きキューから最小値を取り出す

queue.py

import heapq

mat = [1, 2, 3, 4, 5]

print(heapq.heappop(mat))
print(mat)

mat

>>> 1
>>> [2, 4, 3, 5]

heapq.heappop() は配列の最小値を取り除き、その値を返す
最小値を取り除きたくない場合は mat[0]

#要素を優先度付きキューに追加

queue.py

import heapq

mat = [1, 2, 3, 4, 5]

heapq.heappush(mat, 0)
print(mat)

mat

>>> [0, 2, 1, 4, 5, 3]

heapq.heappush() で配列に要素を追加できる
追加した値が配列内で最小値だった場合には１番最初の要素になる

#最大値を扱う場合

要素の符号を反転させて配列に格納し、取り出したら符号を元に戻す