導入
コンピューティングでは、フィボナッチ ヒープは二項ヒープに似たデータ構造ですが、償却実行時間がより優れています。フィボナッチ ヒープは、1984 年に Michael L. Fredman と Robert E. Tarjan によって設計され、1987 年に初めて科学雑誌に掲載されました。フィボナッチ ヒープは、グラフ内の最短経路を計算するダイクストラのアルゴリズムの漸近時間を改善するために使用されます。 Prim アルゴリズム: グラフの最小重みスパニングツリーを計算します。
フィボナッチヒープという名前は、実行時間の計算に使用されるフィボナッチ数に由来しています。
特に、挿入、最小値の検索、キーの減少、および結合の操作はすべて一定の償却コストを持ちます。削除および最小削除操作の償却コストは O(log n ) です。つまり、空の構造体から開始して、最初のグループからのa操作と 2 番目のグループからのb操作のシーケンスにはO ( a + ( b log n )) かかります。二項ヒープでは、このような一連の操作にはO (( a + b )(log n )) 時間がかかります。したがって、 bがaより漸近的に小さい場合には、二項ヒープではなくフィボナッチ ヒープを使用する方が興味深いものになります。
フィボナッチ ヒープの構造
フィボナッチ ヒープは、ヒープ最小特性を満たすツリーのセットです。つまり、子のキーは常にその父親のキー以上です。これは、最小キーが常にいずれかのツリーのルートにあることを意味します。フィボナッチ ヒープの構造は、一部の操作を「遅延」方式で実行し、作業を後の操作に延期できるという点で、二項ヒープの構造よりも柔軟です。たとえば、2 つのヒープの結合は、2 つのツリー リストを連結するだけで実行され、キー減少操作により親からノードが切り離されて新しいツリーが形成される場合があります。
ただし、望ましい実行時間を得るために、ある時点でヒープ構造に何らかの順序を導入する必要があります。特に、ノードの次数 (つまり、スレッドの数) をかなり低い値未満に保ちます。各ノードの次数は最大でもO (log n ) で、次数kのノードのサブツリーのサイズは次のとおりです。最小F k + 2 。ここで、 F k はk 番目のフィボナッチ数です。これを行うには、各非ルート ノードから最大 1 つの子のみを削除できるというルールを尊重する必要があります。 2 番目のノードが切断されると、そのノード自体が新しいツリーのルートになるようにその親から切断される必要があります。ツリーの数は、ツリーを接続する最小削除操作によって削減されます。
この柔軟な構造の結果、一部の操作には時間がかかりますが、その他の操作は非常に速くなります。償却実行時間分析を使用することで、非常に高速な操作に実際よりも少し時間がかかるかのように見せかけます。この「節約された」時間を (銀行口座のように) 使用して、遅い操作の実際の実行時間を相殺します。特定の時点で後で使用するために節約された時間は、ポテンシャル関数によって測定されます。フィボナッチ ヒープの可能性は次の式で求められます。
- ポテンシャル = t + 2 m
ここで、 tはフィボナッチ ヒープ内のツリーの数、 m はマークされたノードの数です。このノードが別のノードの子になったためにその子の少なくとも 1 つが切り取られた場合、ノードはマークされます (ルートはマークされません)。
したがって、ヒープ内の各ツリーのルートには、予約された時間単位があります。この時間単位は、後でこのツリーを償却コストゼロで別のツリーにリンクするために使用できます。また、マークされた各ノードには 2 つの時間単位が予約されています。ユニットを使用すると、父親の結び目を切ることができます。この場合、ノードはルートとなり、第 2 の時間単位は各ルートと同様にこのノードに格納されたままになります。
