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

Краткое описание

Эффективный алгоритм сортировки на основе структуры данных “куча” (heap). Преобразует массив в двоичную кучу (max-heap), затем многократно извлекает максимальный элемент и перестраивает кучу. Гарантирует O(n log n) во всех случаях и работает in-place с O(1) памяти. Нестабильный алгоритм.

Когда использовать

• Гарантированная производительность — всегда O(n log n) в любом случае (лучший, средний, худший)
• Ограниченная память — O(1) дополнительной памяти, сортировка in-place
• Когда нужна стабильная производительность — нет худшего случая O(n²) как у Quick Sort
• Системы реального времени — предсказуемое время выполнения
• Когда нужна приоритетная очередь — heap sort основан на heap, который является основой priority queue
• Альтернатива Merge Sort с меньшей памятью — когда нужна O(n log n) гарантия, но без O(n) памяти

Когда не стоит использовать:

• Когда нужна стабильность — heap sort не стабильный
• Маленькие массивы — накладные расходы на построение кучи делают его медленнее простых алгоритмов
• Кэш-эффективность важна — heap sort имеет плохую локальность обращения к памяти
• Почти отсортированные данные — не адаптивный, всегда O(n log n)

---

С объяснением логики работы

/**
 * Пирамидальная сортировка (Heap Sort)
 * Принцип: используем структуру данных "куча" (heap) — дерево, где родитель всегда больше детей.
 * Алгоритм:
 * 1. Строим max-heap из массива (наибольший элемент в корне)
 * 2. Извлекаем корень (максимум), помещаем в конец
 * 3. Восстанавливаем heap для оставшихся элементов
 * 4. Повторяем пока есть элементы
 */
 
/**
 * Функция для "просеивания вниз" элемента
 * Восстанавливает свойство max-heap для поддерева с корнем в индексе i
 */
function heapify(arr, n, i) {
    // n - размер кучи
    // i - индекс корня поддерева
 
    // Предполагаем, что наибольший элемент - это корень
    let largest = i;
 
    // Вычисляем индексы левого и правого детей
    // В массиве для элемента i:
    // левый ребенок находится по индексу 2*i + 1
    // правый ребенок находится по индексу 2*i + 2
    const left = 2 * i + 1;
    const 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) {
        // Меняем местами
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
 
        // Рекурсивно "просеиваем" затронутое поддерево
        // Это нужно, потому что после обмена могло нарушиться свойство кучи
        heapify(arr, n, largest);
    }
}
 
/**
 * Основная функция Heap Sort
 */
function heapSort(arr) {
    const n = arr.length;
 
    // ШАГ 1: Строим max-heap из массива (BUILD-MAX-HEAP)
    // Начинаем с последнего родительского узла и идём к корню
    // Последний родитель находится по индексу Math.floor(n/2) - 1
    // Почему? Потому что элементы после этого индекса - листья (не имеют детей)
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
 
    // После этого цикла arr представляет собой max-heap:
    // arr[0] содержит максимальный элемент
    // для каждого i: arr[i] >= arr[2*i+1] и arr[i] >= arr[2*i+2]
 
    // ШАГ 2: Один за другим извлекаем элементы из кучи
    // Проходим от последнего элемента к первому
    for (let i = n - 1; i > 0; i--) {
        // Перемещаем текущий корень (максимум) в конец
        // Это правильная финальная позиция для этого максимального элемента
        [arr[0], arr[i]] = [arr[i], arr[0]];
 
        // После swap максимальный элемент на своём месте в конце
        // Теперь уменьшаем размер кучи на 1 (исключая последний элемент)
        // и вызываем heapify для нового корня
        // Это восстанавливает свойство max-heap для уменьшенной кучи
        heapify(arr, i, 0);
 
        // После каждой итерации: 
        // - последние (n-i) элементов отсортированы и на своих местах
        // - первые i элементов образуют max-heap
    }
 
    // После завершения цикла весь массив отсортирован
    return arr;
}
 
// Пример использования
const numbers = [12, 11, 13, 5, 6, 7];
console.log("Исходный массив:", numbers);
heapSort(numbers);
console.log("Отсортированный массив:", numbers);
 
// Визуализация работы алгоритма для [4, 10, 3, 5, 1]:
// 
// 1. Построение max-heap:
//    [4, 10, 3, 5, 1] -> [10, 5, 3, 4, 1]
//          4                  10
//        /   \               /   \
//      10     3             5     3
//     /  \                /  \
//    5    1              4    1
//
// 2. Извлечение и восстановление:
//    [10, 5, 3, 4, 1] -> swap(10,1) -> [1, 5, 3, 4] | 10
//    [1, 5, 3, 4] -> heapify -> [5, 4, 3, 1] -> swap(5,1) -> [1, 4, 3] | 5, 10
//    [1, 4, 3] -> heapify -> [4, 1, 3] -> swap(4,3) -> [3, 1] | 4, 5, 10
//    [3, 1] -> swap(3,1) -> [1] | 3, 4, 5, 10
//    Результат: [1, 3, 4, 5, 10]

---

С анализом сложностей

/**
 * Пирамидальная сортировка (Heap Sort) с анализом сложности
 * 
 * ВРЕМЕННАЯ СЛОЖНОСТЬ:
 * - Лучший случай:   O(n log n) — даже если массив отсортирован
 * - Средний случай:  O(n log n) — стандартный случай
 * - Худший случай:   O(n log n) — всегда одинаковая сложность
 * 
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
 * - O(1) — сортировка in-place, только константа для переменных
 * - Стек рекурсии: O(log n) в heapify, но можно реализовать итеративно для O(1)
 * 
 * ОСОБЕННОСТИ:
 * - Не адаптивный: всегда O(n log n), не зависит от входных данных
 * - НЕ стабильный: может менять порядок равных элементов
 * - In-place: не требует дополнительной памяти
 * - Гарантированная производительность: нет худшего случая O(n²)
 */
 
function heapify(arr, n, i) {
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(log n)
    // В худшем случае элемент "просеивается" от корня до листа
    // Высота дерева = log n, следовательно максимум log n рекурсивных вызовов
    // 
    // ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: O(log n)
    // Стек рекурсии в худшем случае достигает высоты дерева
    // Можно оптимизировать до O(1) с итеративной версией
 
    let largest = i;
    const left = 2 * i + 1;    // O(1) вычисление
    const right = 2 * i + 2;   // O(1) вычисление
 
    // Три сравнения — O(1)
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest !== i) {
        // Swap — O(1)
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
 
        // Рекурсивный вызов — в худшем случае спускаемся на log n уровней
        heapify(arr, n, largest);
    }
}
 
function heapSort(arr) {
    const n = arr.length;
 
    // ФАЗА 1: ПОСТРОЕНИЕ MAX-HEAP (BUILD-MAX-HEAP)
    // 
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n)
    // Хотя может показаться, что это O(n log n), на самом деле O(n)!
    // 
    // ДОКАЗАТЕЛЬСТВО:
    // - Всего узлов: n
    // - Листья (половина узлов): не требуют heapify
    // - Узлы на высоте h: примерно n/2^(h+1) узлов
    // - Каждому узлу на высоте h нужно максимум h операций
    // 
    // Суммарная работа: Σ(h=0 to log n) [n/2^(h+1) * h]
    //                 = n * Σ(h=0 to log n) [h/2^(h+1)]
    //                 = n * O(1) = O(n)
    // 
    // Интуиция: много листьев требуют 0 работы, мало узлов у корня требуют log n работы
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        // Каждый вызов heapify — O(log n)
        // Но суммарно для всех вызовов — O(n) благодаря математике выше
        heapify(arr, n, i);
    }
 
    // ФАЗА 2: ИЗВЛЕЧЕНИЕ ЭЛЕМЕНТОВ И СОРТИРОВКА
    // 
    // ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n log n)
    // - Внешний цикл: n-1 итераций
    // - Каждая итерация: один swap O(1) + heapify O(log n)
    // - Итого: (n-1) * O(log n) = O(n log n)
    for (let i = n - 1; i > 0; i--) {
        // Swap максимального элемента в конец — O(1)
        [arr[0], arr[i]] = [arr[i], arr[0]];
 
        // Восстанавливаем heap для уменьшенного массива — O(log i)
        // i уменьшается с каждой итерацией:
        // Итерация 1: log n операций
        // Итерация 2: log(n-1) операций
        // ...
        // Итерация n-1: log 1 операций
        // 
        // Суммарно: log n + log(n-1) + ... + log 2 + log 1
        //         = log(n!) ≈ O(n log n) по формуле Стирлинга
        heapify(arr, i, 0);
    }
 
    // ИТОГОВАЯ СЛОЖНОСТЬ:
    // Время:  O(n) [build heap] + O(n log n) [sorting] = O(n log n)
    // Память: O(1) для in-place версии, O(log n) для стека рекурсии
    //
    // СРАВНЕНИЕ С ДРУГИМИ O(n log n) АЛГОРИТМАМИ:
    // 
    // Heap Sort:
    // ✓ Гарантированная O(n log n) производительность
    // ✓ O(1) памяти (in-place)
    // ✗ Не стабильный
    // ✗ Плохая cache locality (прыгает по памяти)
    // ✗ Не адаптивный
    // 
    // Quick Sort:
    // ✓ В среднем быстрее Heap Sort на практике (хорошая cache locality)
    // ✓ O(log n) памяти в среднем
    // ✗ Худший случай O(n²)
    // ✗ Не стабильный
    // 
    // Merge Sort:
    // ✓ Гарантированная O(n log n)
    // ✓ Стабильный
    // ✓ Хорошая cache locality
    // ✗ Требует O(n) дополнительной памяти
    // 
    // КОГДА ВЫБРАТЬ HEAP SORT:
    // ✓ Нужна гарантированная O(n log n) без дополнительной памяти
    // ✓ Системы реального времени (предсказуемая производительность)
    // ✓ Ограниченная память (нельзя использовать Merge Sort)
    // ✗ Нужна стабильность (используйте Merge Sort)
    // ✗ Нужна максимальная скорость на практике (используйте Quick Sort)
 
    return arr;
}
 
// Примеры для демонстрации одинаковой сложности:
 
// ЛУЧШИЙ СЛУЧАЙ: уже отсортирован — всё равно O(n log n)
const best = [1, 2, 3, 4, 5];
// Heap Sort не адаптивный, поэтому всё равно выполнит полную работу
 
// ХУДШИЙ СЛУЧАЙ: обратный порядок — O(n log n)
const worst = [5, 4, 3, 2, 1];
// Та же сложность, что и лучший случай
 
// СРЕДНИЙ СЛУЧАЙ: случайный порядок — O(n log n)
const average = [3, 1, 4, 2, 5];
// Всегда одинаковая производительность

См. также

• heap — структура данных куча