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

Пирамидальная сортировка (HeapSort) — это метод сортировки сравнением, основанный на такой структуре данных как двоичная куча.

Сам алгоритм можно разделить на два этапа:

1. Формирование двоичной кучи.
2. Сортировка данных на основе сформированной двоичной кучи.

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

Теперь можно сказать, что такое двоичная куча — это законченное двоичное дерево, в котором элементы хранятся в особом порядке: значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый вариант называется max-heap, а второй — min-heap. Другими словами, выполняется условие:

// Для max-heap

a[i] >= a[2 * i + 1];
a[i] >= a[2 * i + 2];

индекс i - родитель
индекс 2i + 1 - левый ребенок
индекс 2i + 2 - правый ребенок

Будем хранить данные в виде обычного массива. Именно в таком виде представления данных будет удобно работать с индексами элементов (см. в коде).

WARNING! Далее будет всё для случая сортировки по возрастанию. По убыванию - зеркальте всё, что видите.

Пусть у нас будет дан массив arr[], который нужно отсортировать. Длина массива - n.

Первый шаг: построение бинарной кучи.

Нужно построить бинарную кучу. Делать мы это будем следующим образом:

1. Смотрим на сыновей слева и справа - в массиве это arr[2i+1] и arr[2i+2] - выбираем наибольшего из сыновей и родителя, с которого мы начинали данный шаг.
2. Если этот элемент больше родителя arr[i] - меняем его с arr[i] местами и идем к шагу 1, имея в виду новое положение arr[i] в массиве - будем преобразовать затронутое поддерево. Иначе конец процедуры.