1

ノードをバイナリ ヒープに挿入したい場合、挿入とヒープ化後にヒープ内のノードのインデックスを見つけるにはどうすればよいですか? バイナリ ヒープは配列として表されます。このアルゴリズムを O(log(log(n))) で見つける必要があります。

log n の複雑さでそれを見つける方法は知っていますが、log log n で見つけることができません。

皆さん、ありがとうございました。

4

1 に答える 1

3

ノードが通常どのように挿入されるかを見てみましょう。配列の最後に追加され、ルートに到達するか、親以上になるまで親と交換されます（最小ヒープがあると仮定します）。そのため、この要素からルートへのパスでこの要素の位置を見つける必要があります。ただし、このパスはソートされています (ヒープのプロパティのため)。そのため、バイナリ検索を使用してこのパス内の位置を見つけることができます。パスの長さはO(log n)であるため、二分探索は で機能しO(log(log n))ます。

于 2015-01-01T13:37:18.693 に答える