9

最初にヒューリスティックに基づいて要素の優先度を決定する優先度キューを使用しています。要素がデキューされると、ヒューリスティックが更新され、現在キューにある要素のキーが増加する場合があります。

O(1) キーの減少操作を償却したヒープ (具体的にはフィボナッチ ヒープ) があることは知っていますが、キーの増加操作に同様の境界を持つヒープ構造はありますか?

私のアプリケーションでは、これはパフォーマンスの問題ではありません (バイナリ ヒープは正常に動作します)。これは、単に学術的な好奇心の問題です。

編集：明確にするために、キーを減らすのではなく、キーを増やす操作の時間が O(logn) よりも速いデータ構造を探しています。私のアプリケーションは、ヒューリスティックが優先度を過大評価するため、キーを減らすことはありません。

4

3 に答える 3

1

バイナリ ヒープは、対数の複雑さに打ち勝つにはあまりにも柔軟性がありません。二項ヒープは、より効率的な結合操作を可能にします。

減少キーのパフォーマンスが優れている他のヒープは、ペアリング ヒープと2 ～ 3 ヒープです。

于 2009-06-04T19:34:32.940 に答える
0

実際、フィボナッチヒープでは、キーの増加操作はキーの減少と同じです。IMHO、一部のアルゴリズムで使用されているため、操作に「キーを減らす」という名前を付けるのは伝統にすぎません。しかし、フィボナッチヒープの実装では両方が可能です。

于 2010-06-04T13:48:54.893 に答える
0

二項ヒープは、キー操作を減らすために o(log n) 時間かかります! これはフィボナッチ ヒープよりも遅くありませんか?

于 2009-06-04T19:50:27.900 に答える