Корневой узел максимальной кучи содержит наибольшее значение. Каждый ребенок меньше родителя. Начнем с того же массива, что и в предыдущих нескольких статьях.
Сначала построим кучу.
Затем мы начнем создавать максимальную кучу. Так же, как когда мы строили min-heap, мы начнем с 3-го узла:
этаж (6/2) = этаж (3) = 3
Поскольку 9 имеет только один дочерний узел, 9 будет сравниваться с 3. Если родительский узел меньше дочернего, узлы поменяются местами. Поскольку 9 больше 3, узлы не меняются местами. Переходим ко 2-му узлу.
У 2-го узла двое потомков. Большее из двух - 5, поэтому 5 сравнивается с 2. Поскольку 5 больше 2, два значения меняются местами.
Узел сравнения уменьшается, и мы начинаем сравнение с 1-го узла.
У 1-го узла есть двое потомков. Сравнивают детей. Поскольку 9 больше 5, 9 сравнивается с 7. Число 9 больше 7, поэтому два узла меняются местами.
Мы повторим его еще раз, чтобы убедиться, что достигнуто значение Max-Heap. Начнем с 3-го узла. Поскольку родительский номер 7 больше, чем его дочерний элемент, узлы остаются на своих местах.
Узел сравнения уменьшается, и 2-й узел сравнивается со своими дочерними узлами. Поскольку родительский элемент больше, чем оба его дочерних элемента, узлы остаются на своих текущих позициях.
Узел сравнения уменьшается, и 1-й узел сравнивается со своими дочерними узлами. Поскольку родительский элемент больше, чем оба его дочерних элемента, узлы остаются на своих текущих позициях.
Поскольку в дереве нет изменений, мы можем сделать вывод, что дерево максимальной кучи создано.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает эту структуру данных и многое другое.
