algorithm - ヒープに値を追加および削除するための効率的なアルゴリズム

Question

最大ヒープで値を追加および削除したい場合は、最初に値をヒープの最後に追加してから、必要に応じて上方にパーコレートします。次に、ルート ノードを保存して値を削除し、最大ヒープの末尾にある値を取得して一番上に移動し、必要に応じて下に浸透させ、最後に先頭から保存された値を返します。

これには、多くの比較と値の交換が含まれます。複雑さのクラスが似ているが、最初に最大ヒープに値を追加してから削除する方が効率的なアルゴリズムはありますか?

Answer 1

バイナリ ヒープへの追加には、log(N) 回の比較が必要です。アイテムがどこにあるかを知っていると仮定して、アイテムを削除すると、log(N) の比較が行われます。ヒープからの削除の非効率な部分は、削除したい項目を見つけることです。それにはO(N)時間がかかります。

ちなみに、ヒープの最後のアイテムを取得し、削除したいアイテムの位置に配置し、必要に応じて上下に浸透させることで、削除のパフォーマンスを向上させることができます。例については、アルゴリズムのテキストを参照してください。

より効率的なデータ構造が必要な場合は、バイナリ ヒープ以外の何かが必要です。