私はさまざまな種類のヒープデータ構造を見ていました。
フィボナッチ ヒープは、(1) 挿入、(2) 削除、および (2) 最小要素の検索について、最悪の場合の複雑さが改善されているようです。
Java にはPriorityQueue
、バランスの取れたバイナリ ヒープであるクラスがあることがわかりました。しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?
また、フィボナッチ ヒープの実装はありますjava.util
か?
ありがとう!
私はさまざまな種類のヒープデータ構造を見ていました。
フィボナッチ ヒープは、(1) 挿入、(2) 削除、および (2) 最小要素の検索について、最悪の場合の複雑さが改善されているようです。
Java にはPriorityQueue
、バランスの取れたバイナリ ヒープであるクラスがあることがわかりました。しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?
また、フィボナッチ ヒープの実装はありますjava.util
か?
ありがとう!
いいえ、標準の Java コレクション API には、フィボナッチ ヒープの実装は含まれていません。これがなぜなのかはわかりませんが、フィボナッチ ヒープは減価償却された意味で漸近的に優れていますが、実際には巨大な定数係数があるためだと思います。また、コレクション フレームワークには二項ヒープがありません。これも含めるとよいでしょう。
完全に恥知らずな自己プラグとして、私は自分の個人的な Web サイトに Java でフィボナッチ ヒープを実装しています。どれだけ役立つかはわかりませんが、どのように機能するかを知りたい場合は、良い出発点になると思います。
お役に立てれば!
しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?
おそらく、これらのヒープはバイナリ キーよりもエントリごとのオーバーヘッドが大きいためです。
また、Java.util にフィボナッチ ヒープの実装はありますか?
いいえ、でも
しかし、なぜ彼らはフィボナッチ ヒープを使用しなかったのでしょうか?
主な理由は、フィボナッチ ヒープが役立つのは、1 つの extractMin 操作に多数の reduceKey 操作が接続されている場合に限られるからだと思います。たとえば、ダイクストラのアルゴリズムで使用している場合。
また、Java.util にフィボナッチ ヒープの実装はありますか?
Java.util には実装がありませんが、フィボナッチ ヒープの既存のオープン ソース バージョンを使用して、このトピックに関するいくつかの実験を行いました。私のブログまたはプロジェクトの GitHub リポジトリで見つけることができます。