優先度付きキューのパフォーマンスに関して、バイナリヒープと二項ヒープとフィボナッチヒープ

Question

タイトルに記載されているものの中で、ヒープ実装を使用するかどうかをどのように決定すればよいか、誰かに説明してもらえますか？

問題に応じて、構造のパフォーマンスに関する実装を選択するためのガイドとなる回答が欲しいです。現在、優先キューを実行していますが、この場合に最も適切な実装だけでなく、他の状況で実装を選択できるようにするための基本事項も知りたいです...

他に考慮すべきことは、今回はhaskellを使用しているということです。したがって、この言語での実装を改善するトリックや何かを知っている場合は、私に知らせてください！しかし、以前と同様に、他の言語の使用についてのコメントも歓迎します！

ありがとう！質問が基本的すぎる場合は申し訳ありませんが、ヒープについてはまったく詳しくありません。実装するタスクに直面するのはこれが初めてです...

ありがとうございます！

Answer 1

3番目の記事は http：//themonadreader.files.wordpressにあります。.com / 2010/05 / issue16.pdf 関連。

Answer 2

まず第一に、Haskellで標準ヒープを実装することはありません。代わりに、永続的および機能的ヒープを実装します。従来のデータ構造の機能バージョンは、元のデータ構造と同じくらいパフォーマンスが高い場合がありますが（単純なバイナリツリーなど）、そうでない場合もあります（単純なキューなど）。後者の場合、特殊な機能データ構造が必要になります。

機能的なデータ構造に慣れていない場合は、岡崎のすばらしい本または論文（の章関心：少なくとも6.2.2、7.2.2）。

---

それがすべて頭に浮かんだ場合は、単純なリンクされたバイナリヒープの実装から始めることをお勧めします。 （Haskellで効率的な配列ベースのバイナリヒープを作成するのは少し面倒です。）それが完了したら、岡崎の擬似コードを使用するか、最初から始めることで、二項ヒープの実装を試すことができます。

PS。 このcstheory.seの答えは素晴らしいです

Answer 3

優先度付きキューの操作ごとに時間計算量が異なります。これがあなたのための視覚的な表です ジェネラコディセタグプレ

この画像は、プリンストンの講義スライド

バイナリヒープ：

---

二項ヒープ：

---

フィボナッチヒープ：

注：BinomialヒープとFibonacciヒープは見覚えがありますが、微妙に異なります：

• 二項ヒープ：挿入するたびにツリーを熱心に統合します。
• フィボナッチヒープ：次の削除分まで統合を遅延延期します。

Answer 4

機能的な二項ヒープ、フィボナッチヒープ、ペアリングヒープへの参照： https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

パフォーマンスが本当に問題になる場合は、ペアリングヒープを使用することをお勧めします。唯一のリスクは、そのパフォーマンスが今でも推測であるということです。しかし、実験によると、パフォーマンスは非常に優れています。