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

Визуализация

Данные: Случайные

Данные:

Дерево кучи - для извлечения максимумов

Массив - индексы a[i] совпадают с узлами дерева

Легенда цветов

элемент в куче отсортировано сравниваем потомка просеиваемый элемент обмениваем

Элементов 10

Нажмите "Пуск" или листайте по шагам.

Этап: - Сравнения: 0 Обмены: 0 Шаг: 0 / 0 Сложность по времени: -

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

Идея алгоритма: Мы представляем исходный массив в виде двоичного дерева, где каждый элемент больше или равен своим потомкам. Такая структура называется сортирующей кучей (Max-Heap). В корне этой кучи (первый элемент массива) всегда находится максимальный элемент. Алгоритм просто берет максимум, ставит его в конец массива, а оставшуюся часть дерева восстанавливает, "просеивая" новый корень вниз.

Пирамидальная сортировка: схема построения кучи (Heap Sort)

Пошаговый процесс:

Построение кучи. Проходим с середины массива до его начала и каждый элемент "просеиваем" вниз, чтобы он стал больше своих потомков. На это уходит линейное время O(n).
Извлечение максимумов. Берем максимальный элемент (он находится в a[0]) и меняем его с последним элементом неотсортированной части. Теперь максимальный элемент на своем окончательном месте!
Куча сломалась, потому что в корень попал маленький элемент с конца. Мы просеиваем его вниз, восстанавливая свойство кучи для оставшихся элементов.
Повторяем шаги 2 и 3, пока куча не опустеет.

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

Синонимы названия: Сортировка кучей, Пирамидальная сортировка с просеиванием, Heap Sort.

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

Сложность алгоритма

Пирамидальная сортировка работает быстро всегда. Ей абсолютно неважно, отсортирован исходный массив или перемешан, так как высота двоичного дерева всегда остается логарифмической. Сложность принято записывать через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.

По времени

Показывает, как растет число операций (здесь это сравнения и обмены при просеивании) при росте n. Лейбл "Сложность по времени" под визуализацией - время, которое получилось фактически на ваших данных.

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

По памяти

Показывает, сколько дополнительной памяти нужно алгоритму. Сам входной массив в эту оценку не входит: дополнительной считается память сверх него. Пирамидальная сортировка работает "на месте", поэтому расход минимален.

Характеристика	Оценка	Комментарий
Дополнительная память	O(1)	Сортировка происходит "на месте" без создания копий массивов. Стек вызовов также не тратится, если просеивание реализовано через цикл.

Устойчивость алгоритма

Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов.

Характеристика	Оценка	Комментарий
Устойчивость	Нет	В процессе построения кучи и извлечения корня одинаковые элементы могут меняться местами на большие расстояния, что нарушает их исходный порядок.

Примеры реализации пирамидальной сортировки (Heap Sort)

Код на C

void siftDown(int arr[], int root, int end) {
    // Просеиваем узел вниз, пока у него есть хотя бы один потомок
    while (root * 2 + 1 <= end) {
        int child = root * 2 + 1;   // левый потомок
        int swapIdx = root;         // кандидат на наибольший - сам узел

        // Выбираем большего из двух потомков
        if (arr[swapIdx] < arr[child]) {
            swapIdx = child;
        }
        if (child + 1 <= end && arr[swapIdx] < arr[child + 1]) {
            swapIdx = child + 1;    // правый потомок еще больше
        }
        if (swapIdx != root) {
            // Меняем узел с большим потомком и спускаемся за ним
            int temp = arr[root];
            arr[root] = arr[swapIdx];
            arr[swapIdx] = temp;
            root = swapIdx;
        } else {
            return;                 // узел не меньше потомков - куча цела
        }
    }
}

void heapSort(int arr[], int n) {
    // 1. Построение кучи: просеиваем внутренние узлы снизу вверх
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, i, n - 1);
    }
    // 2. Извлечение максимумов: корень (максимум) уходит в конец
    for (int end = n - 1; end > 0; end--) {
        int temp = arr[0];
        arr[0] = arr[end];
        arr[end] = temp;
        siftDown(arr, 0, end - 1);  // чиним кучу для оставшейся части
    }
}

Код на Python

def sift_down(arr, root, end):
    # Просеиваем узел вниз, пока у него есть хотя бы один потомок
    while root * 2 + 1 <= end:
        child = root * 2 + 1   # левый потомок
        swap_idx = root        # кандидат на наибольший - сам узел

        # Выбираем большего из двух потомков
        if arr[swap_idx] < arr[child]:
            swap_idx = child
        if child + 1 <= end and arr[swap_idx] < arr[child + 1]:
            swap_idx = child + 1   # правый потомок еще больше

        if swap_idx != root:
            # Меняем узел с большим потомком и спускаемся за ним
            arr[root], arr[swap_idx] = arr[swap_idx], arr[root]
            root = swap_idx
        else:
            return   # узел не меньше потомков - куча цела

def heap_sort(arr):
    n = len(arr)
    # 1. Построение кучи: просеиваем внутренние узлы снизу вверх
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n - 1)

    # 2. Извлечение максимумов: корень (максимум) уходит в конец
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end - 1)   # чиним кучу для оставшейся части

Код на JavaScript

function siftDown(arr, root, end) {
    // Просеиваем узел вниз, пока у него есть хотя бы один потомок
    while (root * 2 + 1 <= end) {
        let child = root * 2 + 1;   // левый потомок
        let swapIdx = root;         // кандидат на наибольший - сам узел

        // Выбираем большего из двух потомков
        if (arr[swapIdx] < arr[child]) {
            swapIdx = child;
        }
        if (child + 1 <= end && arr[swapIdx] < arr[child + 1]) {
            swapIdx = child + 1;    // правый потомок еще больше
        }
        if (swapIdx !== root) {
            // Меняем узел с большим потомком и спускаемся за ним
            let temp = arr[root];
            arr[root] = arr[swapIdx];
            arr[swapIdx] = temp;
            root = swapIdx;
        } else {
            return;                 // узел не меньше потомков - куча цела
        }
    }
}

function heapSort(arr) {
    let n = arr.length;
    // 1. Построение кучи: просеиваем внутренние узлы снизу вверх
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        siftDown(arr, i, n - 1);
    }
    // 2. Извлечение максимумов: корень (максимум) уходит в конец
    for (let end = n - 1; end > 0; end--) {
        let temp = arr[0];
        arr[0] = arr[end];
        arr[end] = temp;
        siftDown(arr, 0, end - 1);  // чиним кучу для оставшейся части
    }
    return arr;
}

Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про пирамидальную сортировку - с подробной теорией, задачами и проверочными вопросами.