34

フィボナッチヒープとバイナリヒープの実際のアプリケーションは何ですか？問題を解決するためにそれを使用したときに、いくつかのインスタンスを共有できれば素晴らしいと思います。

編集：バイナリヒープも追加しました。知りたい。

4

4 に答える 4

19

実生活ではめったに使用しません。フィボナッチヒープの目的は、ダイクストラのアルゴリズムの漸近的な実行時間を改善することだったと思います。非常に大きな入力を改善できる可能性がありますが、ほとんどの場合、必要なのは単純なバイナリヒープだけです。

Wikiから：

空の構造で始まる一連の操作の合計実行時間は上記の範囲によって制限されますが、シーケンス内の一部の（ごくわずかな）操作は完了するまでに非常に長い時間がかかる場合があります（特に、削除と削除の最小値の実行時間は線形です。最悪の場合）。このため、フィボナッチヒープやその他の償却データ構造は、リアルタイムシステムには適さない場合があります。

バイナリヒープは、値のセットから最大（または最小）値をすばやく見つけるために使用できるデータ構造です。これは、ダイクストラのアルゴリズム（最短経路）、プリムのアルゴリズム（最小スパニングツリー）、およびハフマン符号化（データ圧縮）で使用されます。

于 2010-09-22T09:24:00.943 に答える
13

フィボナッチヒープについては言えませんが、優先キューではバイナリヒープが使用されます。優先キューは、実際のシステムで広く使用されています。

既知の例の1つは、カーネルでのプロセススケジューリングです。最も優先度の高いプロセスが最初に実行されます。

セットのパーティショニングで優先キューを使用しました。最大のメンバーを持つセットが最初にパーティショニングのために取られることになっていた。

于 2010-10-06T09:33:23.843 に答える
1

ほとんどのシナリオでは、次の複雑さに基づいて選択する必要があります。

  • 挿入
  • 要素を見つける

そして、通常の容疑者は次のとおりです。

  • BST：log(n)挿入して検索
  • リンクリスト：O(1)挿入してO(n)検索
  • ヒープ：
    • O(1)入れる
      • バイナリヒープの平均。https ：//stackoverflow.com/a/29548834/895245を参照してください）
      • フィボナッチで償却。これは平均よりも強く、最悪の場合よりも弱いです。
    • O(1)一般 に、最初の要素のみを検索しますO(n)
      • バイナリヒープの最悪のケース
      • フィボナッチで償却

最悪の場合に達するブロダルキューや他のヒープもありますが、それに値するためにはフィボナッチよりもさらに大きなキューが必要です。O(1)

したがって、アルゴリズムが最初の要素を「検索」して多くの挿入を行うだけでよい場合は、ヒープが適しています。

他の人が述べたように、これはダイクストラの場合です。

于 2015-06-20T06:06:08.123 に答える
0

優先度付きキューは通常、ヒープとして実装されます。例：http ://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

巨大なデータセットから上位N個の要素を計算するには、バイナリヒープを使用して効率的に実行できます（たとえば、大規模なWebサイトでの上位の検索クエリ）。

于 2010-09-22T14:52:33.977 に答える