「Introduction to Algorithm」という書籍で提供されている二項ヒープの減少キーのインターフェイスは次のとおりです。キーが k に減らされるノードの「インデックス」。時間計算量は O(logn)
ただし、通常、リンクされたリストを使用して二項ヒープを実装します。この場合、検索を実行せずに x に直接アクセスすることはできません。これは一般に O(n) です。
この問題を解決する 1 つの方法は、二項ヒープ内の各ノードのポインターを保持することです。これにより、O(1) 内のすべてのノードに直接アクセスできますが、空間の複雑さは O(n) になります。
これに対するより良い解決策を知っている人はいますか？ありがとう！
以前の議論はここにあります。