ヒープの拡張であるところのheapdict

Pythonでは標準で「普通の」ヒープがついてくるが，Dijkstra法などの最短路で使うと遅くなる．DecreaseKeyがついていないためである．

以前，NetworkXの最短路を試したときに，あまりに遅いのでソースを読んでみたら，以前は普通のヒープを使っていた．そのため余分な情報をヒープに追加してしまうので，大規模問題例だとメモリがパンクしてしまう．

そのためには，自分でDecreaseKeyを入れたヒープを実装しても良いのだが，既存のモジュールを使う方が簡単だ．探してみるとheapdictという簡単なモジュールがあるようだ．

https://github.com/DanielStutzbach/heapdict

これは通常の辞書と同じ操作ができるデータ構造に以下の操作を追加したものである．

popitem()：最小の値をもつ要素を返し，ヒープから除く

peekitem():最小の値をもつ要素を返すだけ．

インストールは（環境にもよるがたぶん）pipでできる．

> pip install heapdict

使用法は，こんな感じだ．

from heapdict import heapdict

hd = heapdict() 

#heapdictは辞書と同じように機能する

import random

#iをキー ，一様乱数を値として辞書を構成する

for i in range(10):

    hd[i] =random.randint(10,20) 

for i in range(10):

    #print ( hd.peekitem()) #値の小さい順にpeek

    print(hd.popitem()) #値の小さい順にpop