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

Пирамидальная сортировка (Heap Sort)

Определение и назначение

Heap Sort (пирамидальная сортировка) — это алгоритм сортировки, основанный на структуре данных куча (heap). Он сочетает эффективность O(n log n) с постоянным O(1) использованием дополнительной памяти.

Преимущество: гарантированное время в худшем случае O(n log n), в отличие от QuickSort.

Структура данных: куча (heap)

Куча — это полное бинарное дерево, где каждый родитель больше (max-heap) или меньше (min-heap) своих детей.

Максимальная куча:
        50
       /  \\
      30   20
     / \\
    10  5

Свойство: родитель >= детей

В массиве куча хранится так:

Индексы:  0   1   2  3  4
Массив: [50, 30, 20, 10, 5]

Для элемента с индексом i:
- Левый ребёнок: 2*i + 1
- Правый ребёнок: 2*i + 2
- Родитель: (i - 1) / 2

Идея алгоритма

1. Построить max-heap из массива
2. Экстрахировать максимум (корень) в конец массива
3. Восстановить кучу для оставшихся элементов
4. Повторить шаги 2-3 для всех элементов

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

#include <iostream>
#include <vector>
using namespace std;

// Восстановление свойства max-heap для поддерева с корнем в позиции i
void heapify(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;

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

// Главный алгоритм heap sort
void heapSort(vector<int>& arr) {
    int n = arr.size();

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

    // Шаг 2-3: Экстрахировать элементы из кучи
    for (int i = n - 1; i > 0; i--) {
        // Переместить текущий корень (максимум) в конец
        swap(arr[0], arr[i]);

        // Вызвать heapify для уменьшенной кучи
        heapify(arr, i, 0);
    }
}

// Вспомогательная функция для вывода
void printArray(const vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

    cout << "Исходный массив: ";
    printArray(arr);

    heapSort(arr);

    cout << "Отсортированный массив: ";
    printArray(arr);

    return 0;
}

Вывод:

Исходный массив: 64 34 25 12 22 11 90
Отсортированный массив: 11 12 22 25 34 64 90

Пошаговый пример

Дано: [64, 34, 25, 12, 22, 11, 90]

Шаг 1: Построение max-heap

После heapify:
        90
       /  \\
      34   64
     / \\  / \\
    12 22 11 25

Массив: [90, 34, 64, 12, 22, 11, 25]

Шаг 2-3: Экстрахирование

Итерация 1: Swap 90 и 25, heapify
  [25, 34, 64, 12, 22, 11] | [90]

Итерация 2: Swap 64 и 11, heapify
  [34, 25, 11, 12, 22] | [64, 90]

... и так далее

Результат: [11, 12, 22, 25, 34, 64, 90]

Сложность

Преимущества

1. Гарантированное O(n log n) — в отличие от QuickSort
2. O(1) дополнительная память — сортируем на месте
3. Эффективен для больших наборов данных
4. Предсказуемая производительность

Недостатки

1. Не стабилен — одинаковые элементы могут поменять порядок
2. Плохая локальность кэша — частые прыжки в памяти
3. Медленнее QuickSort на практике — больше операций обмена
4. Сложнее реализовать корректно

Сравнение с другими алгоритмами

Algorithm      Best    Average   Worst    Memory  Stable
─────────────────────────────────────────────────────────
QuickSort      O(n²)   O(n log n) O(n log n) O(log n)  No
MergeSort      O(n log n) O(n log n) O(n log n) O(n)  Yes
HeapSort       O(n log n) O(n log n) O(n log n) O(1)  No
BubbleSort     O(n)    O(n²)    O(n²)    O(1)    Yes

Применение heap sort

Используйте heap sort когда:

• Нужна гарантия O(n log n) в худшем случае
• Критична дополнительная память O(1)
• Нужна предсказуемая производительность для real-time систем

Не используйте heap sort когда:

• Нужна стабильность сортировки (используйте MergeSort)
• Данные находятся в кэше (QuickSort более эффективен)
• Нужна простота реализации

Интересный факт

В стандартной библиотеке C++ std::sort часто использует "интроспективную сортировку" (introsort) — гибрид QuickSort и HeapSort. Она начинает с QuickSort, но переключается на HeapSort, если рекурсивная глубина становится слишком большой, гарантируя O(n log n) в худшем случае.

Итоговые рекомендации

Heap Sort — это классический алгоритм сортировки, который гарантирует O(n log n) за счёт структуры кучи. Хотя он медленнее QuickSort на практике из-за плохой локальности кэша, он остаётся важным для:

• Понимания структур данных
• Real-time систем с жёсткими требованиями времени
• Образовательных целей
• Систем, где дополнительная память критична