フィボナッチヒープ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

計算機科学において、フィボナッチヒープというものがある。それは二項ヒープとよく似たデータ構造であるが、より償却実行時間が短くなる。フィボナッチヒープはグラフ内で最短経路を計算するためのダイクストラアルゴリズムや、グラフの最小スパニングツリーを計算するプリムアルゴリズムのおおよその処理時間を改善するのに用いられる。

特に、挿入、最小値検索、キー値減算、マージの操作は一定償却時間内で完了する。削除と最小値削除の操作は最悪O(log n)時間内で完了する。つまり、空のデータ構造から始めて最初のグループから「a」個の操作を行い、次に二番目のグループに「b」個の操作を行う任意のシーケンスでは、O(a + b log a)の時間で完了する。

二項ヒープでは、このような一連の操作ではO((a + b)log(n))時間かかる。aよりbがおおよそ小さい場合はフィボナッチヒープは二項ヒープよりよくなる。

空の構造から一連の操作にかかる時間は上で述べた範囲内に収まるが、いくつかの(非常にまれな)操作では非常に長い時間かかることがある(特にキー値減算、要素の削除、最小値の削除にかかる時間は、最悪の場合要素数に比例する)。この理由により、フィボナッチヒープ及びそれを用いているデータ構造はリアルタイムシステムにはふさわしくないかもしれない。

フィボナッチヒープの名前は、処理時間を解析する際にフィボナッチ数が使用されたことによる。

[編集] フィボナッチヒープの構造

フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。このことは最小のキーは常にある木のルートにあることを意味する。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木はある規定された形を持っておらず、極端な例ではヒープはすべての要素を一つの木として持っているかもしれないし、深さnの一つの木であるかもしれない。この柔軟さによって、後で行う操作のために作業を後回しにするなど、ある種の操作はいいかげんな作法で行うことができる。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを結合して親からあるノードを切り取ってキー値を減算したり新しい木を作ったりすればよい。

しかしながら、所望の処理時間を達成するためにヒープにあるorderを導入する必要があるかもしれない。特に、ノードの深さ(ここで深さとは子の数を指す)をかなり浅く保とうとするならば、すべてのノードはせいぜいO(log n)の深さでしかなく、深さkのノードをルートとするサブツリーの大きさは少なくともFk + 2となる。ここでFkとはk番目のフィボナッチ数である。それぞれルートでないノードのうちせいぜい一つの子を切り取る決まりを守ると、この目標は達成できる。二番目の子を切り取ると、そのノード自身も親から切り取られて新しい木のルートになる。木がすべてつながっているならば、最小値削除の操作を行うことで木の個数が減少する。

柔軟な構造を持つために、いくつかの操作には非常に長い時間かかるが、他の操作は非常に速く終えることができる。ならし解析を行うと、非常に速い操作は実際にかかる時間よりもほんのちょっとしか長くならないことがわかる。この増えた時間は遅い操作の実際の実行時間から後で引かれる。与えられた量に対して後で使用されるためにとっておかれた時間はポテンシャル関数によって計測される。フィボナッチヒープのポテンシャル関数は次の式によって与えられる。

Potential = t + 2m

ここでtはフィボナッチヒープの木の数でmはマークされたノードの数である。あるノードが持つ子が少なくとも一つ切り取られたならば、そのノードは別のノードの子になるのでマークがつけられる(すべてのルートノードはマークがついていない)。

このようにヒープ内のそれぞれの木のルートノードは1単位時間かかる。この単位時間は償却時間0で他の木と後でリンクするのに使われる。また、それぞれのマークされたノードは2単位時間かかる。1単位時間はそのノードの親から切り取られるのに使われる。またそうなった場合、そのノードはルートノードになってもう1単位時間は他のルートノードと同様にかかるようになる。

[編集] 操作の実装

高速に実装および結合を行うには、すべての木のルートノードを環状にリンクし、双方向リストにする。それぞれのノードの子もまた同様なリストにする。それぞれのノードには子の番号とノードにマークがついているかどうかを維持する。さらに最小のキーを含むルートへのポインタも維持する。

最小値検索の操作は、最小値を含むノードへのポインタを維持しているなら些細なものである。ポインタの維持にはヒープのポテンシャルを変更することはないので、実時間および償却時間は共に一定である。上記のために、結合操作は二つのヒープの木のルートのリストを単純につなぎ合わせることで実装される。この操作は一定時間で処理可能でありまたヒープのポテンシャルも変更しない。また償却時間も一定であることも導かれる。挿入操作は一つの要素を持つ新しいヒープを作りそれを結合すればよい。この操作にかかる時間は一定であり、ポテンシャルは木の数が増えることにより一つ増える。償却時間はまだ一定である。

最小値拡大操作(最小値削除)は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)である。

[編集] 歴史

フィボナッチヒープは1984年にMichael L. FredmanとRobert E. Tarjanの二人によって開発され、1987年に科学雑誌に最初に掲載された。フィボナッチヒープを導入することで、ダイクストラやPrimのアルゴリズムを含めたいくつかのグラフアルゴリズムの実行時間を改善したことで最もよく知られている。