1

私はフィボナッチヒープについて学ぼうとしていました。ヒープに要素を挿入するための擬似コードは次のとおりです。

Fibonacci-Heap-Insert(H,x)
degree[x] := 0
p[x] := NIL
child[x] := NIL
left[x] := x
right[x] := x
mark[x] := FALSE
concatenate the root list containing x with root list H
if min[H] = NIL or key[x]<key[min[H]]
      then min[H] := x
n[H]:= n[H]+1

これが私が理解していなかったいくつかのことです、

  • root list containing xHを含むルートリストとそれを連結する方法とは何ですか？

minを抽出している間、次のようなことを行います。

    Fibonacci-Heap-Extract-Min(H)
     z:= min[H]
     if x <> NIL
         then for each child x of z
            do add x to the root list of H
                p[x]:= NIL
            remove z from the root list of H
            if z = right[z]
                then min[H]:=NIL
            else
                  min[H]:=right[z]
                  CONSOLIDATE(H)
            n[H] := n[H]-1
     return z

（ここに他の機能があります、統合してリンクします、http：//www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html）

  • 前の挿入関数では、子を設定し、xのpをnilとして設定し、minを抽出している間、if <> nil常にfalseになるため、関数を数回呼び出すと、正確なminが得られません。

  • この構造がフィボナッチ「ヒープ」と呼ばれる場合、ヒーププロパティはどこで維持されますか？

  • フィボナッチヒープの代わりにダイクストラのアルゴリズムでバイナリヒープを使用する場合、配列またはリンクリストを使用する場合とほぼ同じくらい時間がかかりますか？

誰かが私が抱えている困難を説明できますか？ありがとうございました。

4

1 に答える 1

2

ここにはたくさんの質問があるので、私はそれらすべてに答えるために最善を尽くします。

最初の質問：フィボナッチヒープは、循環的に二重にリンクされたリストですべて一緒にリンクされたツリーのコレクションとして実装されます。挿入関数がxをルートリストHと連結するように要求する場合、作成したシングルトンノード（x）を取得し、それを既存のすべてのツリーHの循環二重リンクリストに接続するように要求します。

extract-minに関する質問については、擬似コードにエラーがあります。テスト

x <> NIL

する必要があります

z <> NIL

xは関数のその時点で定義されていないため、このコードが記述どおりに機能する可能性はありません。

ヒーププロパティがどのように維持されるかについて：フィボナッチヒープ内の個々のツリーは、個別にヒーププロパティに従います。CONSOLIDATEが呼び出されると、複数のツリーをマージして個々のツリーに戻すことができます。これは、ヒーププロパティが維持される場所です。2つのツリーをマージする場合、フィボナッチヒープは常に、ルート値が大きいツリーを取得し、ルートの値が小さいツリーのルートの子にします。このようにして、結果のツリーはヒーププロパティに従います。

最後に、ダイクストラとヒープ：ヒープベースの優先度付きキューを使用したダイクストラのアルゴリズムは、完了するまでにO（m log n）かかりますが、フィボナッチヒープに基づくダイクストラはO（m + n log n）を取ります。これは、スパースグラフの場合は漸近的に高速です。 。ただし、実際には、フィボナッチヒープは、実装が非常に複雑であり、参照の局所性が悪いため、big-O用語に隠された定数係数が高いため、バイナリヒープよりも遅くなる傾向があります。ただし、ダイクストラのバイナリヒープバージョンは、理論上および実際には、リンクリストまたはソートされた配列でバックアップされたバージョンのダイクストラよりも劇的に高速です。

お役に立てれば！

于 2013-01-11T03:15:05.590 に答える