フィボナッチヒープ
 |
フィボナッチヒープ（英: Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。
フィボナッチヒープの名前は、処理時間を解析する際にフィボナッチ数が使用されたことによる。
概要
[編集]フィボナッチヒープは1984年にMichael L. Fredmanとロバート・タージャンの二人によって開発され、1987年に科学雑誌に最初に掲載された。フィボナッチヒープを導入することで、ダイクストラやPrimのアルゴリズムを含めたいくつかのグラフアルゴリズムの実行時間を改善したことで最もよく知られている。
二項ヒープとよく似たデータ構造であるが、より償却実行時間が短くなる。フィボナッチヒープはグラフ内で最短経路を計算するためのダイクストラ法や、グラフの最小全域木を計算するプリム法の漸近的な処理時間を改善するのに用いられる。
特に、挿入、最小値検索、キー値減算、マージの操作は償却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) |
上記の償却計算量を最悪計算量にしたい場合は、弛緩ヒープ (英: relaxed heap) を用いると良い[1]。
フィボナッチヒープの構造
[編集]
フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の（n 個の）木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離されて新しい木を作る場合がある。
しかしながら、処理時間を抑えるためには、何らかの時点でヒープにある種の秩序を導入しなければならない。特に、ノードの次数(＝ノードが直接持つ子の数)はかなり小さく抑えられる：個々のノードの次数はたかだか O(log n) であり、かつ、次数 k のノードが持つサブツリーの大きさは少なくとも Fk + 2 である（ここで Fk は k 番目のフィボナッチ数）。これを守るために、ルートでないノードからはたかだか一つの子しか切り取れないという規約を作る。二つ目の子を切り取る場合は、そのノード自身も親から切り取って新しい木のルートにする。木全体の数は「最小値の削除」操作によって木同士を繋ぐことで減少する。
柔軟な構造を持つために、一部の操作には長い時間がかかる一方、他の操作は非常に速く終わるということが起きる。走行時間の償却解析においては、「非常に速い操作」の所要時間は実際の所要時間よりも若干長いものとして扱う。この余分な時間は、後に「遅い操作」が実際に要した時間から差し引かれる。後で使うために取っておかれている時間の量は、任意の時点でポテンシャル関数によって計測される。フィボナッチヒープのポテンシャル関数は次式によって与えられる。
ここで t はフィボナッチヒープの中にある木の数、m はマークされたノードの数である。あるノードは、自身が他のノードの子となって以降、自身の子が少なくとも一つ切り取られたならばマークされる（但しルートはマークせず、マークされたノードがルートになった場合はマークを消す）。
従って、ヒープ内のそれぞれの木のルートは 1 単位時間を保持している。この単位時間は後でこの木を他の木と償却時間 0 でリンクするのに使うことができる。また、個々のマークされたノードは 2 単位時間を保持している。このうち 1 単位時間はそのノードを親から切り離すのに使うことができる。もしこれが起きると、そのノードはルートとなり、残る 2 つめの単位時間を他のルートと同様に保持し続けることになる。
操作の実装
[編集]高速に実装および結合を行うには、すべての木のルートノードを環状にリンクし、双方向リストにする。それぞれのノードの子もまた同様なリストにする。それぞれのノードには子の番号とノードにマークがついているかどうかを維持する。さらに最小のキーを含むルートへのポインタも維持する。
最小値検索の操作は、最小値を含むノードへのポインタを維持しているなら些細なものである。ポインタの維持にはヒープのポテンシャルを変更することはないので、実時間および償却時間は共に一定である。上記のために、結合操作は二つのヒープの木のルートのリストを単純につなぎ合わせることで実装される。この操作は一定時間で処理可能でありまたヒープのポテンシャルも変更しない。また償却時間も一定であることも導かれる。挿入操作は一つの要素を持つ新しいヒープを作りそれを結合すればよい。この操作にかかる時間は一定であり、ポテンシャルは木の数が増えることにより一つ増える。償却時間はまだ一定である。
最小値拡大操作(最小値削除)は3つのフェーズに分けて行われる。最初に最小要素を含むルートノードを取り出しそれを削除する。ルートノードの子は新しい木のルートになる。もしその子の数がdならば、すべての新しいルートノードの処理にかかる時間はO(d)でありポテンシャルはd-1増える。それゆえにこのフェーズの償却時間はO(d)=O(log n)になる。
しかしながら最小値拡大操作を完了するには、最小値を持つルートノードへのポインタを更新する必要がある。不幸にも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)になる。
あるノードについてキー値減算操作を行うということは、つまりキーを減算しその結果ヒーププロパティに違反することになったら(新しいキーが親のキーよりも小さくなる)そのノードを親から切り離すことである。もし親がルートノードでなければ、そのノードにはマークがつけられる。もしすでにマークがつけられていたならばそのノードを切り離して親にマークをつける。それをルートかマークされていない頂点に到達するまで上に向かって続ける。この処理中にいくつかの、ここでは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.
