Пирамидальная сортировка: дерево внутри массива

Видеоразбор

Куча — ещё не отсортированное дерево

Бинарная куча — полное двоичное дерево: уровни заполняются слева направо. В максимальной куче каждый родитель не меньше своих детей. Поэтому максимум находится в корне, но порядок между соседними детьми и отдельными поддеревьями не определён.

Узлы со ссылками не нужны. В массиве с индексами от нуля дети позиции i находятся на 2i + 1 и 2i + 2, если эти индексы меньше heapSize. Родитель — на floor((i − 1) / 2). Действующая куча занимает [0, heapSize), а готовый суффикс — [heapSize, n).

Построение снизу вверх

Листья уже удовлетворяют свойству кучи. Начинаем с floor(n / 2) − 1, последнего родителя, и просеиваем родителей вниз, продвигаясь к индексу ноль. К моменту обработки родителя оба его дочерних поддерева уже являются кучами.

Просеивание выбирает большего ребёнка; при равенстве — левого. Если он больше родителя, меняем их местами и продолжаем с позиции ребёнка. Иначе останавливаемся. Для [1, 3, 2] построение меняет 1 и 3, получая [3, 1, 2].

Извлечение и восстановление

Меняем корень с последним действующим элементом и уменьшаем heapSize. Извлечённый максимум оказывается на окончательной позиции. Нарушить свойство кучи теперь может только новый корень: просеиваем его вниз.

Для [3, 1, 2] извлечение даёт [2, 1 | 3]. Префикс уже является кучей. Следующее извлечение даёт [1 | 2, 3], а последний одиночный элемент завершает результат. Зелёные ячейки больше не перемещаются; их узлы исчезают из дерева при уменьшении размера кучи.

Во время просеивания свойство кучи может временно нарушаться вдоль активного пути. После восстановления префикс — максимальная куча, суффикс отсортирован, а любое значение префикса не больше любого значения суффикса. Счётчик сравнений учитывает сравнения значений детей и родителя с выбранным ребёнком. Счётчик обменов учитывает просеивание и извлечение. Проверки индексов не считаются.

Почему сортировка неустойчива

Буквы отмечают исходные элементы и не участвуют в сравнении. Выберите пример «Неустойчивость»: [2a, 2b, 1]. При построении обмены не нужны. Извлечение переносит 2a в конец; восстановление меняет 1 и 2b. Результат — [1, 2b, 2a]. Равные значения поменяли исходный порядок.

Выбор левого ребёнка при равенстве не делает алгоритм устойчивым: далёкие обмены при извлечении всё равно могут переставить равные элементы.

Время и память

Построение снизу вверх занимает O(n): большинство узлов расположено близко к листьям и проходит короткий путь. Суммирование работы по уровням даёт линейную оценку; умножать число всех узлов на высоту дерева слишком грубо.

Сортировка занимает O(n log n) в худшем случае: каждое извлечение может пройти O(log n) уровней. Эта реализация завершает просеивание досрочно. На полностью равных значениях работа линейная, поэтому нельзя обещать Θ(n log n) для каждого входа.

Итеративному алгоритму на месте достаточно O(1) дополнительной памяти. Код ниже копирует вход, поэтому использует ещё O(n) памяти. Плеер также хранит снимки для перемотки: им может потребоваться O(n² log n). Ограничение в 15 элементов относится к визуализации.

function heapSort(input) {
    const a = [...input];
    if (a.some(value => !Number.isFinite(value))) {
        throw new TypeError("Expected finite numbers");
    }
    function siftDown(root, size) {
        while (2 * root + 1 < size) {
            let child = 2 * root + 1;
            const right = child + 1;
            if (right < size && a[right] > a[child]) child = right;
            if (a[child] <= a[root]) break;
            [a[root], a[child]] = [a[child], a[root]];
            root = child;
        }
    }
    for (let root = Math.floor(a.length / 2) - 1; root >= 0; root--) {
        siftDown(root, a.length);
    }
    for (let end = a.length - 1; end > 0; end--) {
        [a[0], a[end]] = [a[end], a[0]];
        siftDown(0, end);
    }
    return a;
}

Как выбрать сортировку

Heap sort гарантирует O(n log n) в худшем случае и требует постоянной дополнительной памяти при работе на месте. Сортировка слиянием может сохранять порядок равных элементов, но для массивов обычно требует буфер. Быстрая сортировка часто эффективна на практике, а её худший случай зависит от выбора опорного элемента и разбиения. Выбор определяется требованиями к устойчивости, памяти и входным данным.