Fibonacchi Heaps and Their Uses in Improved Network Optimization Algorithms(1987)
June 24, 2023Fibonacci heaps(F-heaps)は、ダイクストラアルゴリズムの高速化ために開発された木構造の抽象データ型である。 ノードは、1つの値を保存し、親へのポインタをもつ。 また、2つのポインタによって、同じ階層にある兄弟ノードからなる双方向リストに組み込まれる。 ルート階層にあるノードはいずれも親をもたない。 そのほかにも、削除時に使用されるboolean型の変数がノードごとに1つある。 ヒープにある要素の数\(n\)に対して、要素を償却時間計算量\(O(\log n)\)でき、また、定数の償却時間計算量でほかの主要な操作を行える。
Fibonacchi heapsは、値の追加や削除の後でも、常に子ノードにある値が親ノードにある値以上になるように木構造を維持する。 初期状態のヒープは、nullへのポインタに等しい。 空でないFibonacci heapsであれば、ポインタは最小の値をもつノードをさす。 ヒープにある最小の値を取得する場合、このポインタの先にあるノードの値が返される。 値を追加するときは、値を保存したノードをルートの双方向リストに追加する。 もし追加した値が、もとのヒープの最小値よりも小さければ、ヒープをさすポインタの参照先を追加されたノードに変える。
もっとも計算時間量が大きい操作は最小値の削除である。
まず、最小値をもつノードの子ノードを兄弟ノードがある隣接リストに追加する。
ここから、子ノードの数をノードのランクと呼ぶことにする。
ノードを追加した隣接リストにある兄弟ノードのうち、ランクが等しいノードのペアを選び、値がより大きいノードを他方の子ノードに変更する。
これをランクが等しいノードがなくなるまで続け、最終的に双方向リストにはランクが互いに異なるノードのみが残る。
最小値をもつノードの削除するときの様子を以下に示す。
任意のノードを削除することもできる。 そのノードを\(x\)とすると、\(x\)の子ノードを、\(x\)の兄弟ノードからなる双方向リストに追加し、\(x\)をヒープから除外する。 ただし、連鎖的にほかのノードの位置を変える必要がある場合がある。 あるノードを別のノードの子にするときに、子として移動するノードの真偽値変数にFalseを代入する。 一方、子ノードが削除された親ノードがルートになければ、その真偽値変数にTrueを代入する。 そしてTrueを代入されたノードの親の真偽値変数がTrueであれば、ノードを一つ上の階層に移動させ、親の兄弟にする。 以上の手順でノードを再帰的に移動する。
図の出典はもとの論文です。