ヒープ（優先度付きキュー）
1. ヒープ（優先度付きキュー，二分木）
(1) 概要
データ群内から 最小値を抽出する操作をO(1)で行う　→　何度も最小値を抜き出す問題に適している
データ群内にデータを追加する操作をO(logN)で行う
最大値の抽出は直接は使えない．各データを(-1)倍して使う．
最小値を参照したいだけのときは，抽出して，追加する． 0番目の要素を参照する．
内部的には，木構造を用いている．詳しくは，https://qiita.com/T_Wakasugi/items/dac6eb77a3cace54f95e
(2) 実装方法
heapqモジュールを使う（ちょっと癖があります）
(3) 実装例
code:python
import heapq
a = 4, 0, 10, 2, 8, 6
heapq.heapify(a) # リストaをヒープ化．
print(a) # 0, 2, 6, 4, 8, 10
heapq.heappush(a, 11) # 11を追加
print(a) # 0, 2, 6, 4, 8, 10, 11
heapq.heappush(a, 1) # 1を追加
print(a) # 0, 1, 6, 2, 8, 10, 11, 4
x = heapq.heappop(a) # 最小値(0)を取り出す
print(a) # 1, 2, 6, 4, 8, 10, 11
x = heapq.heappop(a) # 最小値(1)を取り出す
print(a) # 2, 4, 6, 11, 8, 10
2. 拡張版 ヒープ
(1) 任意の要素削除付きヒープ
ヒープでは最小値をO(1)で抽出できるが，それ以外の要素は取り出し（削除）不可能
辞書を併用して，疑似的に任意の要素の削除も可能にする．みなしO(logN)
（癖のある）heapqを元に，オブジェクト指向型に変更
初期化：LazyHeapクラスを作成．引数にリストを与えると，heapq.heapfyと同じ働き
push(x)：xを追加
pop()： 最小値を抽出．ヒープから削除される
get()： 最小値を獲得．ヒープから削除されない
remove(x)：（最小値とは限らない）xを削除
lenでヒープ内のデータ数を獲得
x in でヒープ内にデータxが存在するかを True/Falseで判定可能．O(1)
printでヒープの中身を表示できるが，removeで削除したデータも残っているので注意
参考：https://socha77.hatenablog.com/entry/2020/06/17/012842
code: python
import heapq
from collections import defaultdict
class LazyHeap():
def __init__(self, init_arr=[]):
self.heap = []
self.members = defaultdict(int)
self.removed = defaultdict(int)
self.len = 0
for init_element in init_arr:
heapq.heappush(self.heap, init_element)
self.membersinit_element += 1
self.len += 1
def __len__(self):
return self.len
def push(self, k):
heapq.heappush(self.heap, k)
self.membersk += 1
self.len += 1
def pop(self):
self._clear()
self.len -= 1
self.membersself.get() -= 1
return heapq.heappop(self.heap)
def get(self):
self._clear()
return self.heap0
def _clear(self):
while True:
cand = self.heap0
if self.removedcand > 0:
heapq.heappop(self.heap)
self.removedcand -= 1
else:
return
def remove(self, k):
if self.membersk > 0:
self.removedk += 1
self.membersk -= 1
self.len -= 1
def __str__(self):
return str(self.heap)
def __contains__(self, item):
return True if self.membersitem > 0 else False
# 使用方法
hq = LazyHeap(4, 0, 10, 2, 8, 6) # リストを与えてヒープを生成．空から始めて，後でpushで1つずつ追加してもよい
print(hq) # 0, 2, 6, 4, 8, 10
print(len(hq)) # 6（ヒープ内の要素数）
hq.push(11) # 11を追加
print(hq) # 0, 2, 6, 4, 8, 10, 11
hq.push(1) # 1を追加
print(hq) # 0, 1, 6, 2, 8, 10, 11, 4
print(len(hq)) # 8（ヒープ内の要素数）
x = hq.pop() # 最小値(0)を取り出す
print(hq) # 1, 2, 6, 4, 8, 10, 11
x = hq.pop() # 最小値(1)を取り出す
print(hq) # 2, 4, 6, 11, 8, 10
print(len(hq)) # 6（ヒープ内の要素数）
x = hq.get() # 最小値(2)を獲得する（取り出さない）
print(hq) # 2, 4, 6, 11, 8, 10
print(len(hq)) # 6（ヒープ内の要素数は減っていない）
print(2 in hq) # True（2はヒープ内に存在する）
x = hq.remove(4) # （最小値でない）4を削除する
print(hq) # 2, 4, 6, 11, 8, 10．削除した 4もまだ残っている
print(len(hq)) # 5（ヒープ内の要素数は正しく減っている）
print(4 in hq) # False（4はヒープ内に存在しない）
x = hq.pop() # 最小値(2)を取り出す
print(hq) # 4, 8, 6, 11, 10．削除した 4もまだ残っている
print(len(hq)) # 4（ヒープ内の要素数は正しく減っている）
print(4 in hq) # False（4はヒープ内に存在しない）
x = hq.pop() # 最小値(4? 6?)を取り出す
print(x) # 6（正しい！）
print(hq) # 8, 11, 10．削除した 4もヒープから消えている
print(len(hq)) # 3
3. 番外編
C++にはstd::setやstd::multisetなどがある
ref: https://cpprefjp.github.io/reference/set/set.html
これらを使うと
値の追加，削除，検索：$ O(log(n))
max/minの取得：$ O(1)
で出来るっぽい
Pythonの標準ライブラリには無さそうなので，これらを使いたかったら自力で(2. 拡張版ヒープのように)頑張るか，C++を使うと良さそう
勿論，C++にも優先度付きキュー(std::priority_queue)はある
ref: https://cpprefjp.github.io/reference/queue/priority_queue.html
#ヒープ（優先度付きキュー） #データ構造 #モジュール