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

Пирамидальная сортировка (Heapsort) — это алгоритм сортировки сравнением, который использует абстрактную структуру данных двоичная куча (binary heap). Алгоритм работает за время O(n log n) в худшем, среднем и лучшем случаях и является in-place (не требует дополнительной памяти, кроме нескольких переменных).

Алгоритм шаг за шагом:

1. Построение max-кучи: Преобразуем исходный массив в max-кучу. В max-куче ключ каждого узла больше или равен ключам его потомков. Корень содержит максимальный элемент.
2. Сортировка:
   • Меняем местами корень кучи (максимальный элемент) с последним элементом массива.
   • Уменьшаем размер рассматриваемой кучи на 1 (последний элемент теперь на своём месте).
   • Вызываем процедуру heapify (просеивание вниз) для нового корня, чтобы восстановить свойства max-кучи для уменьшенной кучи.
   • Повторяем процесс, пока размер кучи не станет равным 1.

Реализация на C++ с использованием std::vector:

#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).
• Память: O(1) дополнительной памяти (in-place).
• Устойчивость: Неустойчивый (может менять относительный порядок равных элементов).
• Применение: Полезен в системах реального времени, где важна гарантированная производительность O(n log n) и ограниченная память. В практике C++ чаще используется std::sort, который обычно является гибридным алгоритмом (Introsort), использующим Heapsort как fallback для предотвращения деградации QuickSort до O(n²).