algorithm - バイナリヒープから要素を削除するには?

Question

私が理解しているように、binary heapランダム要素の削除はサポートされていません。からランダムな要素を削除する必要がある場合はどうすればよいbinary heapですか?

明らかに、要素を削除して、ヒープ全体を再配置できますO(N)。私はもっ​​とうまくやれるだろうか？

Answer 1

はいといいえ。

問題は、バイナリ ヒープが任意の要素の検索をサポートしていないことです。それを見つけること自体O(n)です。

ただし、要素へのポインター (およびその値だけでなく)がある場合は、要素を右端のリーフと交換し、このリーフを削除してから、関連するサブヒープを再ヒープ化できます (新しく配置された要素をふるいにかけることにより)必要なだけ）。これによりO(logn)削除されますが、探している実際の要素へのポインターが必要です。

Answer 2

アミットは彼の答えで正しいですが、ここにもう1つのニュアンスがあります:

削除されたアイテムの位置 (一番右の葉を置く場所) をバブルアップする必要がある場合があります (親と比較して、親が自分より大きくなるまで上に移動します)。バブルダウンが必要な場合もあります (子供と比較して、すべての子供が自分よりも小さくなるまで下に移動します)。それはすべて場合によって異なります。