1

二項ヒープ構造では、最小ノードを指すポインターしかわかりませんが、任意のノードのキーを減らすにはどうすればよいですか? この場合、まず、このノードを見つけてから、O(lgN) 時間でスワップを実行する必要があります。

私はオンラインで検索し、ノードを減らす方法を多く指摘していますが、このノードにアクセスして減らす方法については言及していません。

編集：

ヒープの各ノードを指すポインターを使用する必要があります。

4

1 に答える 1

1

ここで何かが足りないかもしれませんが、「任意のノード」の鍵を持っている場合は、O(lg n)時間検索を使用してそれを見つけ、オンラインで見つけたアルゴリズムを使用してそれを減らすことができませんか?

于 2011-10-14T23:20:20.400 に答える