ヒープ系データ構造。

実行時間・メモリ要求量がグラフによって影響を受けにくいヒープ系データ構造について、まとめていく。

ある資料によると、元の Dijkstra 法が 1959 年、候補枝を格納するためのデータ構造に binary heap を採用したのは 1964 年に Williams によって行われたようだ。

まず、計算量は O(m x log(n)) (n : 点数、m : 枝数）である。

特徴としては以下のようで、「良くも悪くも安定している」データ構造であるということだ。

・木構造により、最悪時でもあまり低速化されない。
・グラフの特性を用いてないので、あまり効率的でない？



実際に実装し、実験を行って得た情報を踏まえると以下のようにいえる。

・実行時間はヒープに格納されている点数によって決まる。（それでも log が効くため安定する）
・配列で実装しても、ハードウェアプリフェッチに乗せるのは難しい。
・データの局所性はある程度守られる。



ヒープ系データ構造は、やはり安定した動作をするデータ構造であるといえる。どうようなグラフであっても、安定した実行時間で解けるので、特性が分からない場合でも使いやすい。また、Multi-Level-Bucket の３分の１程度しかメモリ要求がなく、それ以上の実行速度も併せ持つので、本当に安定したデータ構造を使いたい場合だけでなく、メモリ要求量も抑えたい場合でもおすすめしたい。