背景
Pythonのheapqを一度でも使ったことがある競プロerなら、その直感的でない記法をなんとかしてほしいと思ったことがあるはず。わざわざ優先度付きキュー専用のリストを作り、そのキューにpushしたりキューからpopしたいときに
heappush(q, (優先度, 値))
や
pri, val = heappop(q)
などと書くのはあまりにも直感に反する。dequeなら
q = deque()
と生成でき、appendやpopしたいときも、
q.append(値)
や
val = q.pop()
と書ける。heapqも同じように書きたいと思ったことは一度や二度ではないだろう。
neoheapq
そこで、こう書けるように新しいクラスを作った。名付けてneoheapq。
python neoheapq.py
import heapq
class neoheapq:
def __init__(self):
self.q = []
def push(self, h:float, val:any) -> None:
heapq.heappush(self.q, (h,val))
def pop(self) -> tuple[float,any]:
return heapq.heappop(self.q)
def __getitem__(self, idx) -> tuple[float,any]:
return self.q[idx]
def __len__(self) -> int:
return len(self.q)
概要
内部でリストを作り、heapq.heappushとheapq.heappopを動かしている。それだけ。
使い方
生成
q = neoheapq()
heapifyに相当する機能は競プロにはあまり要らなさそうだったので作ってない。
追加
q.push(優先度, 値)
pop
pri, val = q.pop()
popを呼ぶと、もっとも優先度が小さいものの(優先度, 値)のタプルがpopされる。
最初のものを取得
pri, val = q[0]
q[0]で、qのうちもっとも優先度が小さいもののタプル(優先度, 値)が返される。heapqと同じくq[1]以降は優先度順になっておらず、あまり意味がないので注意。
値の数
len(q)
最後に
これを使ってダイクストラ法のサンプルコードを作ろうと思ったんですが、面倒なので誰かやってください (丸投げ)