フィボナッチヒープ

フィボナッチヒープとは

フィボナッチヒープは、計算機科学におけるヒープデータ構造の一種です。このデータ構造は、1984年にマイケル・L・フレッドマンとロバート・タージャンの二人によって開発され、1987年に初めて発表されました。フィボナッチヒープの名前は、その処理時間を解析する際にフィボナッチ数が用いられたことに由来します。

概要

フィボナッチヒープは、ダイクストラ法やプリム法などのグラフアルゴリズムの実行時間を改善するために導入されました。二項ヒープと似た構造を持ちますが、より短い償却実行時間を持つことが特徴です。特に、挿入、最小値検索、キー値減算、マージの操作は償却O(1)時間で完了し、削除や最小値削除の操作は償却O(log n)時間で完了します。

計算量

フィボナッチヒープの操作における計算量は以下の通りです。

挿入: 償却O(1)時間
最小値検索: 償却O(1)時間
キー値減算: 償却O(1)時間
マージ: 償却O(1)時間
削除: 償却O(log n)時間
最小値削除: 償却O(log n)時間

これらの計算量は償却時間であり、一連の操作全体での平均的な計算量を表します。最悪の場合、一部の操作には時間がかかることがあるため、リアルタイムシステムには適さない場合があります。

構造

フィボナッチヒープは、minimum-heap propertyを満たす木の集合です。つまり、あるノードの子のキーは常に親のキー以上になります。最小のキーは常にいずれかの木のルートにあります。二項ヒープと比較して、フィボナッチヒープの構造はより柔軟で、木は特定の形状を持つ必要はありません。

柔軟性と遅延処理

フィボナッチヒープの柔軟な構造により、一部の操作を遅延させることが可能です。例えば、二つのヒープを結合する際には、単純に二つのヒープの木のリストを連結するだけで済みます。また、「キーの減算」操作では、ノードが親から切り離されて新しい木になる場合があります。

次数とフィボナッチ数

処理時間を抑えるために、ノードの次数（子ノードの数）は小さく保たれます。個々のノードの次数は最大でO(log n)であり、次数kのノードが持つサブツリーの大きさは少なくともFk+2（Fkはk番目のフィボナッチ数）です。

ポテンシャル関数

フィボナッチヒープの償却解析には、ポテンシャル関数が用いられます。この関数は、ヒープの状態を表し、操作の償却時間を計算するために使用されます。フィボナッチヒープのポテンシャル関数は、次のように定義されます。


Potential = t + 2m


ここで、tはヒープ内の木の数、mはマークされたノードの数です。マークされたノードは、子ノードを一つ失ったノードを指します。

操作の実装

フィボナッチヒープの各操作は、以下のように実装されます。

1. 最小値検索: 最小値を持つノードへのポインタを保持しているため、O(1)時間で完了します。
2. 結合: 二つのヒープの木のリストを連結するだけで、O(1)時間で完了します。
3. 挿入: 新しい要素を持つヒープを作成し、既存のヒープと結合します。O(1)時間で完了します。
4. 最小値削除: 最小値を持つルートノードを削除し、その子ノードを新しいルートにします。その後、同じ次数のルートノードを連結し、最小値を更新します。この操作には償却O(log n)時間がかかります。
5. キー値減算: 指定されたノードのキーを減算し、ヒーププロパティに違反する場合は、そのノードを親から切り離し、必要に応じて親ノードをマークします。この操作には償却O(1)時間がかかります。
6. 削除: 指定されたノードのキーを最小にし、最小値削除操作を行います。この操作には償却O(log n)時間がかかります。

まとめ

フィボナッチヒープは、効率的なデータ構造であり、特にグラフアルゴリズムの性能向上に役立ちます。その柔軟な構造と償却時間解析により、多くのアプリケーションで利用されています。しかし、最悪の場合の計算時間を考慮すると、リアルタイムシステムへの導入は慎重に行う必要があります。

参考資料

* Wikipedia: Fibonacci heap

もう一度検索