Самый маленький листовой узел в минимальной куче, используя только операции кучи

Question

Как найти наименьший листовой узел в минимальной куче, используя только операции кучи?

Answer 1

Единственное требование в минимальной куче - каждый узел меньше своего родителя.Таким образом, между листами нет порядка, что означает, что таким листом может быть любой узел во второй половине массива, который используется для хранения кучи.Итак, нужно пройти n / 2 элементов (вторая половина массива) и найти наименьший.

Answer 2

Если это двоичная куча, вы можете взять [floor (n / 2)] + 1, когда n - количество элементов в куче. Это даст вам самый левый крайний узел.