フィボナッチヒープ完全ガイド：構造と償却時間、decrease-keyの仕組み・Dijkstraでの活用法と実装上の注意点
エバープレイ編集部フィボナッチヒープとは（概説）
フィボナッチヒープ（Fibonacci heap）は、グラフアルゴリズムなどで頻繁に行われる「減少キー（decrease-key）」操作を効率よく扱うことを目的に設計されたヒープ（優先度付きキュー）データ構造です。1987年に Michael L. Fredman と Robert E. Tarjan により発表され、償却解析（amortized analysis）に基づいて非常に良好な平均的（償却）時間計算量を示します。特に Dijkstra の最短経路アルゴリズムや Prim の最小全域木アルゴリズムの理論上の高速化に大きな役割を果たします。
構造の概要
フィボナッチヒープは複数の「木（rooted tree）」の集合を根リスト（root list）として持ちます。各木は最小ヒープ条件を満たします（親のキーは子のキー以下）。木の形は固定されず、操作により自由に変化します。重要な点は、木の次数（あるノードの子の数）が「ログオーダー」で制限されることにより、extract-min（最小値の取り出し）などの操作を効率的に行えることです。
- 根リストは双方向連結リストなどで実装されることが多く、任意の木の根を O(1) で追加・削除できます。
- 各ノードはキー、親ポインタ、子へのポインタ、次数（degree）、および「マーク（mark）」ビットを持ちます。マークはカスケードカットのために使います。
主な操作と償却時間
フィボナッチヒープの主要操作とその償却（amortized）時間複雑度は次の通りです。
- make-heap（空のヒープ作成）：O(1)
- find-min（最小要素参照）：O(1)
- insert（挿入）：O(1)（償却）
- union / meld（合併）：O(1)
- decrease-key（キーの減少）：O(1)（償却）
- extract-min（最小要素の削除・取得）：O(log n)（償却）
- delete（任意要素の削除）：O(log n)（償却）※通常は decrease-key を -∞ にしてから extract-min
ここで n はヒープの要素数です。重要なのは decrease-key が O(1)（償却）である点で、これが Dijkstra などでの理論的高速化につながります。
減少キー（decrease-key）とカスケードカットの仕組み
フィボナッチヒープで特徴的なのが「カスケードカット（cascading cut）」です。操作の流れは以下の通りです。
- ノード x のキーを y（y < x.key）に減少する。
- x が根でない場合かつ親 p のキーが依然として x より小さいならば何もしないが、もし x のキーが親 p のキーよりも小さくなると、ヒープ秩序が壊れるため x を親 p から切り離して根リストに追加する（これをカットする）。
- カットしたあと、親 p のマークビットを確認する。もし p が未マークなら p をマークする（最初の子の喪失を記録）。もしすでにマークされていれば p も切り離して根リストに移し、さらにその親について同様の処理を繰り返す（これがカスケードカット）。
こうすることで、木の形が極端に偏ることを抑え、将来的な consolidate（根の統合）での計算量を制御します。カスケードカットにより、1 回の decrease-key は常に O(1) の実作業（多数の単純操作）かつ償却で O(1) に収まることが示せます。
extract-min と consolidate（統合）の詳細
extract-min（最小要素 z を取り除く）では次の手順を実行します。
- 最小根 z を根リストから取り除き、z の全ての子を根リストに移動させる（子の親ポインタを null に設定）。
- 根リスト内に同じ次数（degree）の木が複数存在する可能性があるため、次数ごとに根をひとつにまとめる（consolidate）。
- consolidate は配列 A を用意し、次数 d の木は A[d] に格納し、既に格納がある場合は 2 つの木をリンクして次数を増やし、その結果を再度適切な A[] へ移す。この処理を次数が重複しなくなるまで続ける。
- consolidate に要する時間は、根の数と最大次数に依存します。最大次数が O(log n) に抑えられるため、extract-min は O(log n)（償却）となります。
次数の上界とフィボナッチ数列の関係
フィボナッチヒープの名前の由来は、ノードの次数の下限を保証する解析でフィボナッチ数列が現れる点にあります。具体的には、任意のノード x に対して、x が持つ子のそれぞれの「サイズ（その部分木のノード数）」はある下限を満たしており、これを繰り返すことで次数 d のノードが持つ部分木の最小ノード数はフィボナッチ数列に対応します。
結果として、n 個のノードを持つヒープにおける最大次数 D(n) は O(log n) で、より厳密には D(n) ≤ floor(log_phi n)（phi は黄金比 (1+sqrt(5))/2）という評価が得られます。log_phi n は log_2 n に対して約 1.44 倍の定数を伴う対数です。
潜在関数を用いた償却解析（概略）
フィボナッチヒープの償却解析は潜在関数（potential function）を導入して行われます。よく使われる潜在関数 Φ は次のように定義されます。
- Φ = t + 2m （t は根リストにある木の個数、m はマークされたノードの個数）
この潜在関数を用いると、各操作の実際のコストと潜在関数の増減を合わせた「償却コスト」を見積もれます。例えば：
- insert：実コストは O(1)、根が一つ増えるので潜在が +1。したがって償却 O(1)。
- decrease-key：カットして根リストへ移せば t が増え、切断元のマーク等の変化により潜在が変わるが、総合的に償却 O(1) になる。
- extract-min：コンソリデートにより根の個数が大幅に減り、潜在が下がる分を用いて O(log n) の償却コストに収める。
この方法で、上に示した償却時間の主張が厳密に導かれます（詳細な証明は文献参照）。
実装上の注意点と実践での適用性
理論的には非常に魅力的なフィボナッチヒープですが、実際の実装や実行速度には注意点があります。
- 実装が複雑：ノードのポインタやマーク管理、根リストの連結操作など実装がやや煩雑でバグを生みやすい。
- 定数因子が大きい：償却解析は操作の漸近的な振る舞いを保証するが、実際の単位時間あたりの定数因子は大きく、しばしば pairing heap や binary heap に比べて遅いことがある。
- 用途の選択：decrease-key を大量に行うケース（例えばスパースグラフを対象にした Dijkstra）では理論上の利点が出やすいが、実際のシステムやデータの性質によっては他のヒープの方が高速な場合が多い。
そのため、研究や理論的解析ではフィボナッチヒープが標準例として用いられますが、実システムや競技プログラミングではより単純で実装しやすいヒープが選ばれることが多いです。近年は pairing heap、rank-pairing heap、strict Fibonacci heap、Brodal heap（最悪時間保証を持つがさらに複雑）など派生構造も検討されています。
歴史的背景と発展
フィボナッチヒープは Fredman と Tarjan によって提案され、彼らの論文は多くのネットワーク最適化アルゴリズムの理論的改良に寄与しました。提案以降、より実用的・単純な代替法（例えば pairing heap）が提案され、さらに最悪計算量で同等以上の性能を達成するデータ構造（Brodal heap など）も研究されています。
まとめ（いつ使うべきか）
フィボナッチヒープは次のような特徴を持ちます。
- decrease-key を O(1)（償却）で扱えるため、理論上 Dijkstra の実行時間を O(m + n log n) にするなどの利点がある。
- 構造と解析は美しく教育的価値が高いが、実装の複雑さと定数因子の問題から実運用では必ずしも第一選択ではない。
- 研究やアルゴリズム設計の観点からは非常に重要で、ヒープに関する理解を深めるうえで有益。
実際のコードで選ぶ際は、操作の性質（特に decrease-key の頻度）、実装の複雑さ、性能要件を考慮して、フィボナッチヒープを採用するかどうか判断してください。
