3

O(1)ヒープ内の要素の優先度を下げるときに、償却された時間の複雑さで優先度キューを実装するための効率的なデータ構造であることがわかりました。ただし、CLRS の教科書によると、優先順位を下げる操作は、ターゲット要素を保持しているノードが既知であることを前提としています。最小ノードではない場合、目的のノードを効率的に取得する方法に興味があります。単純な実装と分析O(n)では、フィボナッチ ヒープで検索操作を実行するために、最悪の場合の時間の複雑さが生じます。これは、他の操作と比較して効率的ではありません。私の質問は、フィボナッチヒープに効率的な検索操作があるか、それとも必要ですか?

4

2 に答える 2

8

まず最初に、この構造は検索構造ではなく効率的な優先キューになるように設計されているため、検索操作はO(n). 通常、変更したい正確なノードを知っています。例を見てみましょう - ダイクストラのアルゴリズム。

すべてのステップで、グラフの頂点をヒープにプッシュするか、その優先度を変更するため、頂点のヒープ ノードへのポインターを保持するのが自然です。この方法でうまくいきます！

したがって、基本的には、ノードへのポインターをどこかに保存します (ハッシュマップまたは AVL ツリーに保存できます)。

于 2013-06-05T15:21:53.970 に答える