Повторная настройка двоичной кучи после удаления минимального элемента

Question

После удаления минимального элемента в двоичной куче, т. Е. После удаления корня, я понимаю, что куча должна быть скорректирована, чтобы сохранить свойство кучи. Но предпочтительный способ сделать это - назначить последний лист корню и просеять его вниз.

Мне интересно, почему мы не берем младшего ребенка того, что раньше было корнем, а просто продолжаем просеивать всех детей? Разве это не то же самое количество операций, так почему же предпочтителен метод «присвоить последний лист корню и просеять вниз»?

Answer 1

Потому что вы должны держать дерево заполненным с левой стороны в последнем ряду. Взбираясь сверху вниз, вы не можете гарантировать, что последний элемент, который вы поднимите вверх, будет самым правым элементом.