heap queueを自分で実装してみる - ラシウラプライオリティキュー実装としてよくつかわれるpythonのheapqモジュールのソースは、ばらばらのリストをheap化するheapifyのようなものがあったり、細かい効率化などもあって、そのソースコードは結構な大きさです。 基本はそうたいそうなものではないので、訓練として自らの手で実装してみました。heapを空リストから追加前提にし、アルゴリズム部分をなるべくシンプルに書いてみると、このくらいになりました。 http://gist.github.com/224175 heap操作の理解のためのメモ heapは、二分木の配列表現の一種: インデックスが1始まりだとすると、インデックスnの子は2nと2n+1になる たとえば、1の子は2と3、2の子は4と5、3の子は6と7のようにかぶることは無い CやPythonのように0始まりの場合は、2n+1と2n+2 さらに、すべてのノードで、親の値は子の
