問題タブ [decrease-key]

多くの高速優先度キュー（フィボナッチヒープやペアリングヒープなど）は、優先度キューにすでに格納されている要素を取得してその優先度を効率的に下げるキー減少操作をサポートしています。フィボナッチとペアリングヒープの場合、優先キューから要素を削除して後で再挿入するよりも、減少キーを実行する方が高速です。

順序付けられた辞書構造（二分探索木、スキップリストなど）で同様の操作をサポートできるかどうか疑問に思っています。具体的には、順序付けられた辞書があり、あるキーと値のペアのキーを別のキーに変更したいとします。順序付けられた辞書の標準表現で、時間O（1）またはO（log log n）でこれを行うことは可能ですか？バランスの取れたBSTを使用すると、要素を削除して再挿入することでO（log n）時間でこれを実行できるため、興味がありますが、これを実行するより高速な方法があるようです。

ありがとう！

Prim のアルゴリズムを実装しようとしています。そのためには、優先度キューの reduceKey メソッドが必要です (優先度キューのキー値を更新するため)。これを STL Priority Queue に実装できますか?

それが役立つ場合、これは私が従っているアルゴリズムです:

• グラフ G の各頂点 u に対して
  • u のキーを INFINITY に設定
  • u の親を NIL に設定する
• ソース頂点のキーを 0 に設定
• 上記のキーを使用して、グラフ内のすべての頂点を優先度キュー Q にキューに入れます。
• Q は空ではありません
  • Q の最小キーで頂点 u をポップする
  • u の各隣接頂点 v について
    • (v がまだ Q にある) かつ (key(u) + weight-function(u, v) < key(v)) の場合
      • u を v の親に設定する
      • update v's key to equal key(u) + weight-function(u, v) // この部分で問題が発生します。これは、優先度キューに reduceKey を実装する方法がわからないためです

フィボナッチ ヒープのキーの減少操作で O(1) の償却複雑さを取得するにはどうすればよいですか? 要素を含むフィボナッチ ヒープ内のノードを見つけるだけでも、BFS を使用して O(n) 時間かかるため、O(1) 償却時間を取得することはできません。

参考までに、問題のノードを検索するための BFS の実装を次に示します。

そして、ここに私の減少キーのコードがあります:

「Introduction to Algorithm」という書籍で提供されている二項ヒープの減少キーのインターフェイスは次のとおりです。キーが k に減らされるノードの「インデックス」。時間計算量は O(logn)

ただし、通常、リンクされたリストを使用して二項ヒープを実装します。この場合、検索を実行せずに x に直接アクセスすることはできません。これは一般に O(n) です。

この問題を解決する 1 つの方法は、二項ヒープ内の各ノードのポインターを保持することです。これにより、O(1) 内のすべてのノードに直接アクセスできますが、空間の複雑さは O(n) になります。

これに対するより良い解決策を知っている人はいますか？ありがとう！

以前の議論はここにあります。

実装でブーストからフィボナッチヒープを使用しようとしていますが、減少関数を呼び出すとプログラムがクラッシュします。これは例です(Wは単純なクラスです):

Java の Priority Queue が ChangePriority をサポートしていないのはなぜだろうと思っていました。ChangePriority を削除すると、より効率的な実装を使用できるようになることをどこかで (詳細なしで) 読みましたが、それがどのように可能になるかわかりません。バイナリ ヒープは非常に単純で効率的なデータ構造のようです。改善の余地はありません。もう 1 つの手がかりは、どの要素 (おそらくヒープ内の位置) が優先度を変更するかを PQ に示すのにぎこちないインターフェイスが必要になる可能性があることですが、それでも結論を出すには Java の初心者です。

編集: なぜこれは無意味な質問ではないのでしょうか? Java を初めて使用する場合 (特に C/C++ のバックグラウンドを持っている場合)、すべてのポインターがどこにあるのか、または Java で Dijkstra をどのように実装するのかなどについて疑問に思うようになります。

最初の質問には何度も回答がありましたが、2 番目の質問には、私が理解している限り、単純な回答がありません。Java のような言語では、すぐに使える通常のプログラミング ツールがすべて手元にあり、素敵なクラス ラッパーにカプセル化されていると期待できます。しかし、突然、キーを減らすメソッドを使用して PQ を自分で実装する必要があります。これは、おそらく C/C++ よりも Java で行う方が厄介なことです。この質問では、ダイクストラの実装方法を尋ねているわけではありません (これは他のスレッドで適切に回答されています)。キー/プリオの減少方法なしでは分類できない PQ の多くのアプリケーションがまだ存在する可能性があります。PQ のアイテムよりもはるかに多くの優先度の更新がある場合。ダイクストラでは、最大で V

したがって、Java の PQ に変更の優先度がないのには、いくつかの深刻な理由があると考える人もいるかもしれません。その理由は、実際の Java の PQ インターフェイスに関係なく、おそらく興味深いものです。

Binomial Heap の Python 実装を探していますが、コードに reduceKey が実装されていないことに気付きました。二項ヒープでは、誰もreduceKeyを実装していないのはなぜですか?