私が理解しているように、binary heap
ランダム要素の削除はサポートされていません。からランダムな要素を削除する必要がある場合はどうすればよいbinary heap
ですか?
明らかに、要素を削除して、ヒープ全体を再配置できますO(N)
。私はもっとうまくやれるだろうか?
私が理解しているように、binary heap
ランダム要素の削除はサポートされていません。からランダムな要素を削除する必要がある場合はどうすればよいbinary heap
ですか?
明らかに、要素を削除して、ヒープ全体を再配置できますO(N)
。私はもっとうまくやれるだろうか?
はいといいえ。
問題は、バイナリ ヒープが任意の要素の検索をサポートしていないことです。それを見つけること自体O(n)
です。
ただし、要素へのポインター (およびその値だけでなく)がある場合は、要素を右端のリーフと交換し、このリーフを削除してから、関連するサブヒープを再ヒープ化できます (新しく配置された要素をふるいにかけることにより)必要なだけ)。これによりO(logn)
削除されますが、探している実際の要素へのポインターが必要です。
アミットは彼の答えで正しいですが、ここにもう1つのニュアンスがあります:
削除されたアイテムの位置 (一番右の葉を置く場所) をバブルアップする必要がある場合があります (親と比較して、親が自分より大きくなるまで上に移動します)。バブルダウンが必要な場合もあります (子供と比較して、すべての子供が自分よりも小さくなるまで下に移動します)。それはすべて場合によって異なります。