Fibonacchi Heaps and Their Uses in Improved Network Optimization Algorithms(1987)
Fibonacci heaps(F-heaps)は、ダイクストラアルゴリズムの高速化ために開発された木構造の抽象データ型である。 ノードは、1つの値を保存し、親へのポインタをもつ。 また、2つのポインタによって、同じ階層にある兄弟ノードからなる双方向リストに組み込まれる。 ルート階層にあるノードはいずれも親をもたない。 そのほかにも、削除時に使用されるboolean型の変数がノードごとに1つある。 ヒープにある要素の数\(n\)に対して、要素を償却時間計算量\(O(\log n)\)でき、また、定数の償却時間計算量でほかの主要な操作を行える。