Макс-куча заказа

Question

Если A [1 .. n] - это максимальная куча, где могут быть второй, третий, четвертый ... самые большие элементы массива?

[1]

[2] [3]

[4] [5] [6] [7]

Answer 1

Давайте сделаем так: самый большой элемент находится в корне.Кто является кандидатами на 2-е место и 3-е место?Ответ -> Непосредственные дети корня.Зачем?Потому что все элементы ниже потомков root будут меньше, чем потомки root.

Точно так же, кто является кандидатом на четвертое место?Дочерние элементы 2-го и 3-го самых больших элементов, то есть узлов от индекса 4 до индекса 7.

Answer 2

Как известно, первым элементом является максимум. За ним следуют его дети в позициях 2 * k и 2 * k + 1. Так что, если вы основаны на 1, следующие цифры в размере 2 и 3.