Журов Евгений Владимирович
КУРСОВАЯ ЗАДАЧА - ПИРАМИДА
Создайте метод пирамидальной сортировки.
Описание метода:
Метод базируется на понитях «Куча»(пирамида) и «Просеивание». Куча — это двоичное дерево, у которого каждый родитель имеет значение: большее либо равное значениям своих потомков (свойство кучи).
«Просеивание» — обмен узлового элемента с его максимальным потомком, если узловое значение меньше значения потомка. У узла может быть 2 потомка, 1 потомок или не быть потомков (листья дерева).
Шаг 1)
Приводим массив к куче с помощью «просеивания». Дерево можно хранить в плоском виде в массиве: узел лежит по индексу i, то потомки лежат по индексам: 2i + 1 и 2i + 2
Правая часть массива уже удовлетворяет правилу кучи, потому что явялется листьями и не имеет потомков. Цель, добиться выполнения условия для любого узла: array[i] >= array[2i + 1] и array[i] >= array[2i + 2]
Когда Вы меняете узловой элемент с наследником требуется перепроверка, не сломала ли перестановка кучу, потому что узел сам может являться потомком. Провека и перестановки должны делаться до тех пор, пока не будет восстановлено свойство кучи. Когда массив удовлетворяет свойству кучи, элемент с индексом 0 принимает максимальное значение.
Шаг 2)
Меняем 0 индекс с максимальным элементом с последним элементом в массиве
Шаг 3)
Поскольку последний элемент уже отсортирован, то длина сортируемого массива уменьшится на 1.
Шаг 4)
Когда был переставлен максимальный элемент в шаге 3, массив перестал быть кучей. Вызываем рекурсию, чтобы восстановить кучу и снова пройти по всем шагам. Не забываем про условие выхода из рекурсии.
Требования к оформлению.
При использовании встроенных методов сортировок, коллекций, стримов и материала выходящего за рамки пройденного курса задача не принимается к проверке.