問題タブ [fibonacci-heap]

Fibonacci-Heapを実装したことがある人はいますか? 私は数年前にそうしましたが、配列ベースの BinHeaps を使用するよりも数桁遅かったです。

当時、私はそれが、研究が必ずしも主張されているほど優れているとは限らないことについての貴重な教訓だと考えていました. ただし、多くの研究論文は、フィボナッチ ヒープの使用に基づくアルゴリズムの実行時間を主張しています。

効率的な実装を作成できたことがありますか? それとも、フィボナッチ ヒープがより効率的になるほど大きなデータセットを扱っていましたか? もしそうなら、いくつかの詳細をいただければ幸いです。

私はJavaでのフィボナッチヒープの実装に約1週間取り組んできました。これは、CLRSブックに基づいた実装です。

JavaのデフォルトのPriorityQueueと比較して、作業中のサイドプロジェクトでそれを使用してパフォーマンスが向上するかどうかを確認したかったのです。[Javaのデフォルトの実装は配列ベースであるため、はるかにローカルです。複雑さの限界が高いにもかかわらず、それでもFヒープを上回る可能性があります]。

私の問題は、min要素を削除した後のヒープの統合部分に起因しているようです。arrayindexoutofboundsexceptionsがスローされ続けます。特にwhileループでは、同じ次数を持つすべてのノードを統合します。D（）関数で設定された範囲を超えています。

したがって、私のD（）関数が間違っているか、そうではないと思います。または、何か他のことが起こっています。最も可能性の高い副作用関連。

コードはここにあります。私はこれを約1週間デバッグしようとしてきましたが、運が良かったです。明らかな何かが欠けていますか？

JGraphTには素晴らしいフィボナッチヒープクラスがあります。これを使用して、プリムの最小スパニングツリーアルゴリズムを実装するにはどうすればよいですか？

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

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

フィボナッチ ヒープを使用したダイクストラの実装を考案しようとしています。私が理解しようとしているのは、O(logn) (削除あり) の最小距離以外に、特定のノードの隣接ノードを表すことができるかどうかです。それとも、これはフィボナッチ ヒープ構造に違反していますか? そうしないと、隣人リストとフィボナッチ ヒープを作成する必要があります。

私はプリムのアルゴリズムとその実装を知っていますが、いつも私が今聞きたい部分をスキップします。フィボナッチヒープを使用したプリムのアルゴリズムの実装は次のとおりであると書かれておりO(E + V log(V))、私の質問は次のとおりです。

• 簡単にフィボナッチヒープとは何ですか?
• それはどのように実装されていますか？と
• Prim のアルゴリズムをフィボナッチ ヒープでどのように実装できますか?

私はさまざまな種類のヒープデータ構造を見ていました。

フィボナッチ ヒープは、(1) 挿入、(2) 削除、および (2) 最小要素の検索について、最悪の場合の複雑さが改善されているようです。

Java にはPriorityQueue、バランスの取れたバイナリ ヒープであるクラスがあることがわかりました。しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?

また、フィボナッチ ヒープの実装はありますjava.utilか?

ありがとう！

私は、プライオリティ キューを実装して、比較的シンプルな Astar の効率的な実装を可能にすることに関心があります (プライオリティ キューはシンプルです)。

スキップ リストは単純な O(1) の抽出最小操作と O(Log N) の挿入操作を提供するため、O(log N) の抽出を持つフィボナッチ ヒープを実装するのがより困難な場合と競合する可能性があります。 Min と O(1) の挿入。まばらなノードを持つグラフには Skip-List が適しているのに対し、ノードが密に接続されている環境にはフィボナッチ ヒープが適していると思います。

これにより、通常はフィボナッチ ヒープが改善される可能性があります。

Is there any heap based on Pell sequence(or Pell number) instead of Fibonacci number(like the Fibonacci heap)?

CLRS の Introduction to Algorithms 3rd edition P.525 で、サイズ (x) の下限を分析すると、「ノードに子を追加してもノードのサイズを減らすことができないため、Sk の値が増加するため」と引用した文があります。 k" で単調に。しかし実際には、Sk が k に対して単調に増加するとは限らないことを示す反例を示すことができると思います。次のグラフでは、key=1 のノードの次数は 2 で、次数が 2 のノードは他にありません。つまり、S2=8 です。同様に、Ｓ３＝６である。しかし、現在、S3 は S2 より小さく、つまり、Sk は k に対して単調に増加していません。

ヒープは、一連のカットとカスケード カットを実行することにより、順不同の二項サブツリーから派生できます。

上記の構造が有効なフィボナッチ ヒープかどうかを知りたいです。もしそうなら、それは有効な反例でもあります。