algorithm - 最小要素を削除した後にバイナリ ヒープを再調整する

Question

バイナリヒープの最小要素を削除した後、つまりルートを削除した後、ヒーププロパティを維持するにはヒープを調整する必要があることを理解しています。しかし、これを行うための好ましい方法は、最後の葉を根に割り当ててふるいにかけることです。

なぜ私たちは根であったもののより小さな子を取り出さず、すべての子をふるいにかけ続けるのか疑問に思っています. これは同じ量の操作ではないのに、なぜ「最後の葉をルートに割り当ててふるい落とす」方法が好まれるのでしょうか?

Answer 1

最後の行の左側からツリーをいっぱいにしておく必要があるためです。上から下にふるいにかけると、上にふるいにかけた最後の要素が一番右の要素になるとは限りません。