ヒープの「削除」操作（最大または最小ではない）がO（n）を取るのはなぜですか？

Question

ヒープ上の削除操作はO(n)（注意：最大値または最小値ではありません）とすることが知られています。ヒープは削除や更新には適していませんが、ちょっと不思議です。

私は、特定の要素を削除したい場合は、私はちょうどpercDown(element)考えるとheapSize--それが行わ作る....だから私はそれがO(logn)を取ると考えていることと思いますか？

私は何かを見逃しましたか？

Answer 1

あなたは、配列ベースの完全なバイナリツリーの実装について話していると思います。

短い答えは、必要ではないということです。ヒープ内のオブジェクトからそれらが格納されているインデックスまでのパラレルマップを維持すると、sifting操作を使用してO（ログn）内で削除して、削除によって作成された「穴を埋める」ヒーププロパティを復元できます。

ナイーブな実装では、ヒープ配列の検索によって開始されるため、O（n）が必要です。これをO（n）より効率的にするのに役立つヒーププロパティについては何もありません。

オブジェクトのインデックスをヒープノード内に保持するのではなく、インデックスのヒープを保持するhere is an implementationと、オブジェクト内のインデックスをとる逆インデックス（整数の配列のみ）配列をヒープ配列のインデックスに追加します。この逆マップは、他の操作の漸近実行時間を変更しませんが、O（log n）の削除を提供します。