フィボナッチヒープ
【英】：Fibonacci heap
ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O
となりうるが, 
回の挿入, 
回の最小値の取り出し, 
回の値の減少を行う合計の計算時間が O
となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.
| 組合せ最適化： | パーフェクトグラフ予想 ヒープ ファセット制約 フィボナッチヒープ マッチング問題 メタヒューリスティクス ラグランジュ緩和法 |
フィボナッチヒープ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/05/03 01:59 UTC 版)
|
フィボナッチヒープ（英: Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。
フィボナッチヒープの名前は、処理時間を解析する際にフィボナッチ数が使用されたことによる。
概要
フィボナッチヒープは1984年に Michael L. Fredman とロバート・タージャンの二人によって開発され、1987年に科学雑誌に最初に掲載された。フィボナッチヒープを導入することで、ダイクストラ法やプリム法を含めたいくつかのグラフアルゴリズムの実行時間を改善したことで最もよく知られている。
二項ヒープとよく似たデータ構造であるが、より償却実行時間が短くなる。フィボナッチヒープはグラフ内で最短経路を計算するためのダイクストラ法や、グラフの最小全域木を計算するプリム法の漸近的な処理時間を改善するのに用いられる。
特に、挿入、最小値検索、キー値減算、マージの操作は償却 O(1) 時間内で完了する。削除と最小値削除の操作は償却 O(log n) 時間内で完了する。つまり、空のデータ構造から始めた場合、最初のグループの「a」個の操作、および二番目のグループの「b」個の操作からなる任意のシーケンスは、O(a + b log a) の時間で完了する。
二項ヒープでは、このような一連の操作では O((a + b)log(n)) 時間かかる。よってaよりbが漸近的に小さい場合はフィボナッチヒープは二項ヒープよりよい。
空の構造から一連の操作にかかる時間は上で述べた範囲内に収まるが、（非常にまれだが）いくつかの操作では非常に長い時間かかることがある（特にキー値減算、要素の削除、最小値の削除にかかる時間は、最悪の場合要素数に比例する）。この理由により、フィボナッチヒープ及びそれを用いているデータ構造はリアルタイムシステムにはふさわしくないかもしれない。
計算量
| 操作 | 最悪計算量 | 償却計算量 |
|---|---|---|
| 最大値の取得 | O(1) | O(1) |
| 要素数の取得 | O(1) | O(1) |
| 追加 | O(1) | O(1) |
| 削除 | Ω(n) | O(log n) |
| 値の更新 | Ω(n) | O(1) |
フィボナッチヒープの構造
フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の（n 個の）木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離されて新しい木を作る場合がある。
しかしながら、処理時間を抑えるためには、何らかの時点でヒープにある種の秩序を導入しなければならない。特に、ノードの次数(＝ノードが直接持つ子の数)はかなり小さく抑えられる：個々のノードの次数はたかだか O(log n) であり、かつ、次数 k のノードが持つサブツリーの大きさは少なくとも Fk + 2 である（ここで Fk は k 番目のフィボナッチ数）。これを守るために、ルートでないノードからはたかだか一つの子しか切り取れないという規約を作る。二つ目の子を切り取る場合は、そのノード自身も親から切り取って新しい木のルートにする。木全体の数は「最小値の削除」操作によって木同士を繋ぐことで減少する。
柔軟な構造を持つために、一部の操作には長い時間がかかる一方、他の操作は非常に速く終わるということが起きる。走行時間の償却解析においては、「非常に速い操作」の所要時間は実際の所要時間よりも若干長いものとして扱う。この余分な時間は、後に「遅い操作」が実際に要した時間から差し引かれる。後で使うために取っておかれている時間の量は、任意の時点でポテンシャル関数によって計測される。フィボナッチヒープのポテンシャル関数は次式によって与えられる。
-
図1のフィボナッチヒープに最小拡大の最初のフェーズを適用したもの。キー1を持つノード(最小)が削除され、その子が分離した木として追加された。 最小値拡大操作(最小値削除)は3つのフェーズに分けて行われる。最初に最小要素を含むルートノードを取り出しそれを削除する。ルートノードの子は新しい木のルートになる。もしその子の数がdならば、すべての新しいルートノードの処理にかかる時間は O(d) でありポテンシャルはd-1増える。それゆえにこのフェーズの償却時間は O(d)=O(log n) になる。
図1のフィボナッチヒープに最小拡大を完全に適用したもの。最初に3と6のノードを一緒にリンクする。そしてノード2をルートとする木につなげる。最後に新たに最小ノードが見つかる。 しかしながら最小値拡大操作を完了するには、最小値を持つルートノードへのポインタを更新する必要がある。不幸にもn個までのルートノードをチェックする必要があるかもしれない。二番目のフェーズでは、同じ次数のルートノードを一緒につなげてルートノードの数を減らす。uとvという二つの同じ次数のルートノードがあった場合、一方を子にしてよりキー値が小さいもう一方をルートのままにしておく。そのルートの次数は一つ増える。この操作をすべてのルートが異なる次数になるまで繰り返し行う。同じ次数の木を効率的に検索するために、O(log n) の長さを持つ配列を用意し、それぞれの深さのあるルートへのポインタを保持するようにする。2番目に同じ深さのルートが見つかったならば、その二つの木を結合して配列の内蔵を更新する。二番目のフェーズ開始時のルートの数がmとすると、実実行時間は O(log n + m) になる。最後に、高々 O(log n) 個のルートになる(それぞれのルートは異なる次数になっている)。それゆえにポテンシャルは少なくとも m - O(log n) 減り償却時間は O(log n) になる。
3番目のフェーズではルートとして残っているものをチェックして最小値を検索する。これには O(log n) の時間がかかりポテンシャルは変化しない。最小値拡大操作の全体の償却時間は O(log n) になる。
図1のフィボナッチヒープでノード9のキーを0に減らしたもの。2つのマークされた祖先と同様にこのノードは1をルートとする木から切り取られ新しくルートとして配置される。 あるノードについてキー値減算操作を行うということは、つまりキーを減算しその結果ヒーププロパティに違反することになったら（新しいキーが親のキーよりも小さくなる）そのノードを親から切り離すことである。もし親がルートノードでなければ、そのノードにはマークがつけられる。もしすでにマークがつけられていたならばそのノードを切り離して親にマークをつける。それをルートかマークされていない頂点に到達するまで上に向かって続ける。この処理中にいくつかの、ここではkとする、新しい木を作成する。これらの新しい木は恐らく最初の一つを除いてもともとマークされていたが、ルートになるのでマークされなくなる。一つのノードはマークされうる。それゆえにポテンシャルは少なくともk - 2減る。切り取るのにかかる実時間は O(k) かかる。それゆえに償却時間は一定である。
最後に削除操作は、単に削除する要素のキーを無限に減らす、つまりヒープ全体の中で削除対象の要素のキーを最小にするというように実装される。これをノードを削除するための最小拡大と呼ぶ。この操作にかかる償却時間は O(log n) である。
脚注
- ↑ Driscoll, James R.; Gabow, Harold N.; Shrairman, Ruth; Tarjan, Robert E. (November 1988). “Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation”. Communications of the ACM. doi:10.1145/50087.50096.
- フィボナッチヒープのページへのリンク
