Это классический алгоритм сортировки который, пожалуй, должен знать любой программист. В основу данной сортировки заложен принцип построения "Кучи". Куча - это структура данных, которая удовлетворяет следующему свойству: значения потомков всегда меньше, его родителя. У одного родителя не может быть больше двух потомков. Таким образом, мы всегда имеем максимальное значение из всего подмножества в вершине кучи.
Алгоритм сортировки состоит из следующих шагов:
1. Построение кучи.
Кучу всегда можно легко построить используя массив:
Вершина кучи это всегда первый элемент массива.
Левый потомок идентифицируется по индексу 2*i + 1.
Правый потомок идентифицируется по индексу 2*i + 2.
2. Меняем местами первый и последний элемент.
3. Восстанавливаем кучу (операция просеивания) для N-1 элементов.
Временная сложность алгоритма O(N*log N).
На практике может применяться для нахождения k-го максимального элемента (для этого не требуется полная сортировка массива).
Обработка протестирована на версии платформы 1С:Предприятие 8.3 (8.3.12.1616).
