なぜ新しいノードをヒープに挿入するときに1 + logNの比較が必要なのですか？

私は、新しいノードをヒープに挿入するときに、通過する可能性のあるノードの量がlogNであると思います。それはなぜ（1 + logN）ですか？なぜ新しいノードをヒープに挿入するときに1 + logNの比較が必要なのですか？

1つの要素を持つヒープに 'log（1）= 0'が挿入されるため、比較が行われます – harold

ありがとうございます。私はこれが正解でなければならないと思います。 – user1888955

これは、ノートの数が2の場合の境界ケースを考慮する必要があります。ⁿです。 Nレベルのヒープは、一つより多くのオブジェクトが新しいレベルを開始追加ので、2つの^N -1オブジェクトにフィット：

黒四角を3レベル・ヒープの7つの要素を表します。赤い要素は8番です。検索でこの最後の要素の場所に移動すると、ログ 8が3であっても、4つの比較が行われます。

2017-02-12 01:14:58 dasblinkenlight

あなたの答えに感謝しかし、私は4つの比較がある理由を理解していません。私にとっては、新たに追加された赤い四角が泳いでも3回しか見えません（3回の比較：赤い線、緑の線、青い線、合計3回） – user1888955

@ user1888955あなたはroot、rootの子と比較する必要があります、ルートの孫、赤いノード自体を検索して、探しているアイテムが見つかったことを確認します。 – dasblinkenlight

あなたのクイック返信ありがとうございます:)私はノード自体の比較を逃した。 – user1888955

答えて