38

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

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

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

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

ありがとう!

4

3 に答える 3

53

いいえ、標準の Java コレクション API には、フィボナッチ ヒープの実装は含まれていません。これがなぜなのかはわかりませんが、フィボナッチ ヒープは減価償却された意味で漸近的に優れていますが、実際には巨大な定数係数があるためだと思います。また、コレクション フレームワークには二項ヒープがありません。これも含めるとよいでしょう。

完全に恥知らずな自己プラグとして、私は自分の個人的な Web サイトに Java でフィボナッチ ヒープを実装しています。どれだけ役立つかはわかりませんが、どのように機能するかを知りたい場合は、良い出発点になると思います。

お役に立てれば!

于 2011-06-08T03:24:43.310 に答える
5

しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?

おそらく、これらのヒープはバイナリ キーよりもエントリごとのオーバーヘッドが大きいためです。

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

いいえ、でも

  1. Nathan Fiedlerのグラフメーカー(GPL) があり、テスト カバレッジも良好ですが、これについて、およびフィボナッチ impl が持つ可能性がある問題について、この素敵なブログ投稿を参照してください。この投稿では、他の多くの Java 実装が参照されています。
  2. ここに単体テストを含むコードがあります
  3. JGraphTプロジェクト(Nathan Fiedler も) と (いくつかのマイナーな)テストを使用していますが、LGPL です。
  4. 最後になりましたが、Neo4j - GPL - テストなしです。
于 2012-01-15T15:15:15.200 に答える
1

しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?

主な理由は、フィボナッチ ヒープが役立つのは、1 つの extractMin 操作に多数の reduceKey 操作が接続されている場合に限られるからだと思います。たとえば、ダイクストラのアルゴリズムで使用している場合。

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

Java.util には実装がありませんが、フィボナッチ ヒープの既存のオープン ソース バージョンを使用して、このトピックに関するいくつかの実験を行いました。私のブログまたはプロジェクトの GitHub リポジトリで見つけることができます。

于 2015-02-12T18:56:10.010 に答える