Алгоритм пирамидальной сортировки (Heap Sort): принцип работы

Также упоминается как: Сортировка кучей, Хипсорт, Пирамидальная сортировка с просеиванием

Пирамидальная сортировка - это великолепный алгоритм сложности O(N log N), который, в отличие от турнирной сортировки или сортировки слиянием, вообще не требует дополнительной памяти. Сортировка происходит "на месте" внутри самого массива.

Идея метода сортировки

Алгоритм рассматривает обычный массив как структуру "Двоичная куча" (Max-Heap). В куче значение каждого узла больше либо равно значениям его потомков. Корень кучи всегда лежит в arr[0], а дети узла i лежат по индексам 2*i + 1 и 2*i + 2.

1. Построение кучи: Идем от середины массива к началу, выполняя для каждого элемента операцию Просеивание (SiftDown). Массив превращается в max-кучу, и абсолютный максимум оказывается в индексе 0.
2. Сортировка: Берем arr[0] (максимум) и меняем его с последним элементом массива. Теперь максимум стоит на своем законном месте!
3. Размер "кучи" условно уменьшаем на 1. Новый arr[0] нарушает свойство пирамиды, поэтому мы "просеиваем" его вниз, пока он не найдет свое место. Следующий максимум всплывает на вершину. Повторяем процесс, пока куча не опустеет.

Ниже можно в динамике изучить механику пирамидальной сортировки: от построения двоичной кучи до поочередного просеивания элементов.

Реализация на C

Операция SiftDown (Просеивание)

void Swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }

// Просеивание элемента вниз по пирамиде
void SiftDown(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) {
        Swap(&arr[i], &arr[largest]);
        // Рекурсивно просеиваем дальше вниз (можно сделать циклом без рекурсии)
        SiftDown(arr, n, largest);
    }
}

Сам алгоритм пирамидальной сортировки

void HeapSort(int arr[], int n) {
    // 1. Построение кучи (начинаем с последнего узла, у которого есть дети: n/2 - 1)
    for (int i = n / 2 - 1; i >= 0; i--) {
        SiftDown(arr, n, i);
    }

    // 2. Сортировка: последовательно извлекаем максимум
    for (int i = n - 1; i >= 0; i--) {
        Swap(&arr[0], &arr[i]); // Максимум в конец
        SiftDown(arr, i, 0);   // Просеиваем новый корень в куче размера 'i'
    }
}