Сортировка кучей (пирамидальная сортировка, heap sort)

Это классический алгоритм сортировки который, пожалуй, должен знать любой программист. В основу данной сортировки заложен принцип построения "Кучи". Куча — это структура данных, которая удовлетворяет следующему свойству: значения потомков всегда меньше, его родителя. У одного родителя не может быть больше двух потомков. Таким образом, мы всегда имеем максимальное значение из всего подмножества в вершине кучи.

Алгоритм сортировки состоит из следующих шагов:

1. Построение кучи.

Кучу всегда можно легко построить используя массив: 

Вершина кучи это всегда первый элемент массива.

Левый потомок идентифицируется по индексу 2*i + 1.

Правый потомок идентифицируется по индексу 2*i + 2.

2. Меняем местами первый и последний элемент.

3. Восстанавливаем кучу (операция просеивания) для N-1 элементов.

Временная сложность алгоритма O(N*log N).

На практике может применяться для нахождения k-го максимального элемента (для этого не требуется полная сортировка массива).  

Обработка протестирована на версии платформы 1С:Предприятие 8.3 (8.3.12.1616).