フィボナッチヒープ – ウィキペディア

Posted on May 14, 2019 by lordneo

before-content-x4

コンピューターサイエンスには、 フィボナッチヒープ （英語 ヒープ 「Halde」）優先キューを実現する二項頭に似たデータ構造。これは、任意の順序で定義された優先度を持つ要素をヒープで効率的に保存できることを意味し、要素は常に最優先事項で常に削除できることを意味します。要素の優先順位はキーに感銘を受けます。したがって、たとえば、数値全体にわたって小等しい関係（≤）を表すように、キーの量よりも合計順序が必要です。フィボナッチヘップは、1984年にマイケルL.フレッドマンとロバートE.タルジャンによって最初に説明されました。彼らの名前は、フィボナッチ数が主要な役割を果たしているデータ構造の分析に由来しています。

after-content-x4

fibonacci-hepsは操作を効率的にサポートしています。

入れる – 要素を挿入するには、
削除また消去 – 要素を削除するには、
getmin – 最小キーの要素を見つけるには、
Extractmin – 最小限のキー、つまり最優先事項で要素を返して削除するために、
DecoseSeyKey – 要素のキーを減らすため
マージ また連合 – 2つのHEPの融合用。

すべての操作は、対数最悪の用語、つまり

{displaystyle {mathcal {o}}（log n）}

$mathcal{O}(log n)$ 、実装、したがって n 現在ヒープ内にある要素の数はそうです。操作のみ削除、 Extractmin と DecoseSeyKey 最悪の場合、線形用語が必要です。

{displaystyle {mathcal {o}}（n）}

${mathcal {O}}(n)$ 。ただし、他のほとんどすべての操作のコストは償却されます。

{displaystyle {mathcal {o}}（1）}

${mathcal {O}}(1)$ 。

その結果、フィボナッチヘップは、償却稼働時間分析を伴う操作の実行における二分のhepまたは二項HEPSです 入れる と マージ 検討。しかし、それらは悪い最悪の期間に適しています削除、 Extractmin と DecoseSeyKey 個々の操作を効率的に実行する必要があるオンラインアルゴリズムの場合。

比較期間：

after-content-x4

（*）償却費
（**）よく知られている位置で、そうでなければ

{displaystyle {mathcal {o}}（log n）}

$mathcal{O}(log n)$ *

このフィボナッチヒープには、グレード0、1、3の3つの木があります。3つのノットがマークされています。したがって、ヒープの可能性は9（3本の木 + 2×3のマークされたノット）です。

フィボナッチヒープは、秩序ある後継者を持つ木のリストで構成されており、その結び目にはキーとおそらくマーキングが含まれています。キーに感銘を受けた各ノードの優先順位は、少なくとも子供の優先事項と同じくらい大きいです。これはヒープ条件と呼ばれます。ここに示されているものと ミンヒープ より大きな優先度は、より小さなキーによって示されます。

循環的な二重吸引リストは、木のリストと、木のノード内の子ノードのリストの両方に使用されます。

さらに、ポインターは、最優先事項、つまり最小のキーで、要素上で管理されます。

フィボナッチの頭がそうするでしょう 正規化 すべての木が異なる程度の根を持っている場合、i。 H.リスト内の木の根がすべて異なる多くの子ノードを持っている場合。

フィボナッチヒープは、最小ヘッドプロパティを満たす木のコレクションです。 H.子供の鍵は、常に父親の鍵よりも大きいか等しくなります。これは、最小のキーが常に木の1つの根元にあることを意味します。二項HEPと比較して、フィボナッチヒープの構造はより柔軟です。木には処方された形がなく、極端な場合には、ヒープには別の木に要素があります。この柔軟性により、一部のプロセスを実行することができます。これは、後のプロセスの作業によって引き起こされるものです。たとえば、HEPのマージは、単に木の2つのリストをチェックすることによって、操作は DecoseSeyKey 時々、彼の包括的なノードから結び目を切り取り、新しいツリーを形成します。

ただし、ある時点で、目的の用語を達成するために、ヒープに注文を導入する必要があります。特に、ノードの程度（ここでは子供の数を意味します）は非常に低く保たれます。

{displaystyle {mathcal {o}}（log n）}

$mathcal{O}(log n)$ そして、kのノードに根付いている部分ツリーのサイズは少なくとも f _K+2、それによって f _k k -te fibonacci番号。これは、ルートノード以外のノードからのみ子供を切り取ることができるというルールによって達成されます。 2番目の子供が遮断されている場合、ノード自身が包括的なノードから切り取られ、新しいツリーの根元になる必要があります。木の数は操作中です Extractmin 木がリンクされている場所を減らします。

構造が緩んでいるため、一部の操作には時間がかかる場合がありますが、他の操作は非常に迅速に実行されます。償却されたランニング時間分析では、非常に高速なプロセスが実際よりも少し時間がかかるふりをすることにより、潜在的な方法を使用します。この追加時間は後で結合され、実際の用語から遅い操作が控除されます。後で使用するために節約される時間は、常に潜在的な関数によって測定されます。フィボナッチヒープの可能性はによって与えられます ポテンシャル= t + 2m 。

木の数はフィボナッチヒープにあり、 m マークされたノットの数。この結び目が別のノードの下位結び目になったため、彼の下位ノードの少なくとも1つが切断された場合、結び目がマークされます。すべての根はマークされていません。操作の償却用語は、実際の時間の合計と c – 場合によっては、ポテンシャルの違いがあります c 定数です。

したがって、各ツリーの根は、ヒープに時間単位を節約しました。この時間単位は、後でこのツリーを償却時間0に別のツリーとリンクするために使用できます。さらに、マークされた各結び目に2つの時間ユニットが保存されます。包括的な結び目から結び目を切り取ることができます。この場合、ノードはルートになり、2番目の時間単位は他のルートにその中に保存されたままです。

Table of Contents

手術入れる [ 編集 | ソーステキストを編集します ]

の場合、要素を挿入する場合 入れる これが単に別のツリーとして木のリストに挿入され、必要に応じて、挿入された要素のキーが以前の最小要素のキーよりも小さい場合、ポインターが最小要素に更新される場合。したがって、用語は一定です。

{displaystyle {mathcal {o}}（1）}

${mathcal {O}}(1)$

手術マージ [ 編集 | ソーステキストを編集します ]

それを使用して2つのHEPのマージも同様に簡単です マージ 。ここで、マージツリーのリストは単にチェーンされ、追加されたヒープの最小要素のキーが以前の最小要素の鍵よりも小さい場合、ポインターは最小要素に実装される場合があります。この用語は再び一定です：

{displaystyle {mathcal {o}}（1）}

${mathcal {O}}(1)$

手術 DecoseSeyKey [ 編集 | ソーステキストを編集します ]

キーを結び目9から0に減らした後、フィボナッチの頭と、この結び目とその2つの顕著な祖先は、ルート1で木から切り取られ、新しいルーツとして配置されます。

また、操作 DecoseSeyKey フィボナッチヒープで非常に怠zyな実行されます。更新される要素の鍵は、最初に新しい値に配置されます。今、それはヒーププロパティ、つまりH.すべての子供は父親よりも大きく、もはや満たされていません。これを復元するために、更新された要素は、父親のノードの子供のリストから削除され、別の木として木のリストに挿入されます。

ヒープ操作がそのような操作を通じて大きく成長しすぎることを避けるために、それは Extractmin 非常に長い間、あなたは1つの子供のノードのみが各結び目から削除される可能性があるという状態を配置します。そうしないと、ノード自身を父親のノードの子リストから削除する必要があります（手順切る）これを実現するために、上記のノードのマーキングが表示されます。ノットは、ルートリストのノードではない場合に正確にマークされ、子供は子供リストから削除されました。父親がマークされた子供が削除されるようになった場合、あなたは手順を呼び出します切る父親への再帰。頻繁に数学的な分析の後、程度の木の結び目の数が

{displaystyle k}

$k$ 、d。 H.木の根があります

{displaystyle k}

$k$ 子供たち、そしてを通して

{displaystyle（k+2）}

$(k+2)$ -e fibonacci番号

{displaystyle f_ {k+2} geq varphi ^{k}}

$F_{k+2} geq varphi^k$ それによって底に限定されています

{displaystyle varphi}

$varphi$ ゴールデンカット

{displaystyle {frac {1+ {sqrt {5}}} {2}}}}}

$frac{1+sqrt{5}}{2}$ は。これは関数用です Extractmin 非常に重要です。

[ 編集 | ソーステキストを編集します ]

最小キー1の結び目が削除され、その下位要素が別々の木として追加されました。

手術を完了した後のフィボナッチヘッド Extractmin 。まず、ノード3と6が接続されています。次に、結果はルート2のツリーにリンクされます。

今、中心的な関数へ： Extractmin 。この関数の開始は非常に単純です。ポインターが示す最小要素が発行され、すべての子供が個々の木としてルートリストに追加され、要素自体がヒープから削除されます。これで、新しい最小値を決定する必要があります。ただし、以前の機能のいずれもヒープを深く伸ばすことはないため、これには線形時間がかかります。したがって、ヒープは事前に手順とともに使用されます掃除 “クリーンアップ”。その後、ルートリストのすべての要素は、新しい最小値を見つけるために行われます。

手順掃除：このため、アレイが最初です

{displaystyle a}

$A$ から

{displaystyle 0}

${displaystyle 0}$ それまで

{displaystyle 2cdot log n}

${displaystyle 2cdot log n}$ 初期化。これは、次のようにする必要があります掃除それ以外の

{displaystyle d}

$d$ ルートリストに程度の要素がある場合、木の上にポインターが立っています

{displaystyle d}

$d$ 存在した。したがって、ルートリストのすべての要素は、この配列に分類されます。 2つの要素が同じ程度を持っているときにオーバーラップがある場合、他の要素の父親の小さなキーで要素が作成され、その程度が増加し、配列に分類されます。上記の数学分析は、せいぜいそれを保証します

{displaystyle 2cdot log n}

${displaystyle 2cdot log n}$ 配列内の要素をスタンドします。最後に、新しいルートリストを設定する必要があります。これを行うには、配列のすべての要素が

{displaystyle a}

$A$ 通過してリストに統合しました。その用語はそうです

{displaystyle {mathcal {o}}（log n）}

$mathcal{O}(log n)$ 。

手術削除 [ 編集 | ソーステキストを編集します ]

のためにヒープから要素を削除します削除最初に行われます DecoseSeyKey 削除される要素のキーは、前の最小値よりも小さい値に設定されます。これにより、この要素が新しい最小要素になります。それからそれは可能です Extractmin 除去される。のランタイム DecoseSeyKey の一定です Extractmin に相当します

{displaystyle {mathcal {o}}（log n）}

$mathcal{O}(log n)$ 、したがって、操作があります削除ランタイムも

{displaystyle {mathcal {o}}（log n）}

$mathcal{O}(log n)$ 。

操作削除と DecoseSeyKey 対応する要素の位置がヒープで知られていることを述べています。一般に、ヒープ内の要素を効率的に検索することはできません。したがって、操作 入れる 挿入された要素のコンテナへのポインタを配信します。これは、必要に応じて適切な場所で呼び出しプログラムが覚えています。

Dijkstraのアルゴリズムが最短のパスまたはプリムからのアルゴリズムを見つけて、グラフで最小限のエキサイティングなツリーを見つけること n 結び目と m エッジは、ランタイムとともに使用できます

{displaystyle {mathcal {o}}（ncdot log（n）+m）}

$mathcal{O}(n cdotlog (n) + m)$ 実装する。バイナリまたは二項山では、の条件のみ

{displaystyle {mathcal {o}}（（n+m）cdot log（n））}

$mathcal{O}((n + m)cdot log (n))$ 可能。

マイケル・L・フレッドマン、ロバート・E・タージャン： Fibonacci Heapsと改善されたネットワーク最適化アルゴリズムの使用。の： ACMのジャーナル。 34年目、いいえ。 3 、1987、 S. 596–615 、doi： 10.1145/28869.28874 。

after-content-x4