Что такое пирамидальная сортировка (Heap Sort)?

А, пирамидальная сортировка! Ну это, бля, классика, ёпта. Как старый дедовский способ, но работает — ядрёна вошь — как часы. Представь себе, что ты пытаешься из кучи говна, простите, из кучи случайных чисел, построить этакую пирамидку, где на самом верху самый жирный элемент сидит. А потом этого жирного — хуй с горы — сталкиваешь вниз, на своё законное место. И так раз за разом, пока вся куча не отсортируется. Красота, да?

Вот смотри, как это работает, если по-человечески объяснить.

Смысл всей этой движухи: Алгоритм использует структуру, которая называется двоичная куча (binary heap). Это не какая-то хитрая жопа, а просто массив, который можно мысленно представить как почти полное бинарное дерево. В max-куче (а мы будем строить именно её) родитель всегда больше или равен своим детям. То есть самый большой мудила всегда наверху, в корне.

Делается всё в два больших этапа:

1. Построение max-кучи. Берём наш неупорядоченный массив и начинаем его прогонять через процедуру heapify (просеивание вниз), начиная с последнего родителя. В итоге получаем кучу, где в нулевом индексе лежит максимальный элемент. Волнение ебать — первый шаг сделан.
2. Собственно сортировка. А вот тут начинается магия in-place (то есть на месте, без лишних массивов).
   • Меняем местами этот самый максимальный элемент (корень) с последним элементом массива. Всё, самый большой уплыл в конец, на своё окончательное место.
   • Размер нашей «активной» кучи уменьшаем на единицу (последний элемент больше не трогаем).
   • Но после обмена свойства кучи нарушились! Новый корень — какой-то полупидор. Надо вызвать heapify для нового корня, чтобы восстановить порядок в уменьшенной куче.
   • Повторяем эту пляску: корень -> в конец, уменьшаем кучу, восстанавливаем. Пока от кучи не останется один-единственный элемент. Всё, массив отсортирован.

Вот, смотри, как это в коде выглядит. Блоки кода не трогаю, они святы.

#include <iostream>
#include <vector>
#include <algorithm> // для std::swap

// Просеивание элемента с индексом i вниз в поддереве размера n.
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;       // Инициализируем наибольший как корень
    int left = 2 * i + 1;  // Левый потомок
    int right = 2 * i + 2; // Правый потомок

    // Если левый потомок существует и больше корня
    if (left < n && arr[left] > arr[largest])
        largest = left;
    // Если правый потомок существует и больше текущего наибольшего
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // Если наибольший элемент — не корень
    if (largest != i) {
        std::swap(arr[i], arr[largest]); // Меняем местами
        heapify(arr, n, largest);        // Рекурсивно heapify затронутое поддерево
    }
}

// Основная функция пирамидальной сортировки
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 1. Построение max-кучи (переупорядочивание массива).
    // Начинаем с последнего нелистового узла (индекс n/2 - 1).
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. Извлечение элементов из кучи один за другим.
    for (int i = n - 1; i > 0; i--) {
        // Перемещаем текущий корень в конец
        std::swap(arr[0], arr[i]);
        // Вызываем heapify для уменьшенной кучи (размера i)
        heapify(arr, i, 0);
    }
}

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    heapSort(data);
    for (int val : data) std::cout << val << " "; // 5 6 7 11 12 13
    return 0;
}

Ну и что мы в сухом остатке имеем?

• Сложность: Всегда O(n log n), и в худшем, и в среднем. Это его главная фишка. Не то что QuickSort, который может накрыться медным тазом на неудачных данных.
• Память: O(1). Сортирует прямо на месте, дополнительной памяти — доверия ебать ноль. Экономично.
• Устойчивость: Неустойчивый. Может перепутать местами одинаковые элементы. Если для тебя это критично — ищи другой алгоритм.
• Где это нужно? Ну, в ядре, в реальном времени, где нельзя допустить скатывания в O(n²). Удивление пиздец, но в твоём любимом std::sort он тоже притаился! Тот самый Introsort сначала пытается быстренько отсортировать через QuickSort, но если видит, что тот начинает бздеть и деградировать — переключается на Heapsort, чтобы гарантировать ту самую n log n. Хитро, да?

В общем, алгоритм хоть и не самый быстрый на практике для случайных данных, но надёжный, как хуй в пальто. Знать его стоит, чёрт возьми.