12

タイトルで言及されているものの中で、1つまたは別のヒープ実装を使用するかどうかをどのように決定すればよいか、誰かが私に説明してもらえますか?

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

他に気になる点としては、今回は haskell を使っているので、この言語での実装を改善する裏技や何か知っていることがあれば教えてください! 以前と同様に、他の言語の使用に関するコメントも大歓迎です!

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

再度、感謝します！

4

4 に答える 4

4

http://themonadreader.files.wordpress.com/2010/05/issue16.pdfの 3 番目の記事が関連しているかもしれません。

于 2011-12-03T21:48:19.893 に答える
3

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

関数型データ構造に慣れていない場合は、岡崎の優れた本または論文から始めることをお勧めします (関心のある章: 少なくとも 6.2.2、7.2.2)。

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

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

于 2011-12-04T15:38:26.697 に答える
1

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

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

于 2012-08-17T09:15:50.307 に答える