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

Эффективный алгоритм на основе структуры данных куча (heap).

Куча (max-heap) — это массив, в котором элементы расположены так, что каждый «родитель» больше своих «детей». Если представить массив как дерево, то для элемента с индексом $i$:

левый потомок: $2i + 1$
правый потомок: $2i + 2$

Например, массив [9, 7, 8, 3, 5, 6] — это куча, потому что 9 > 7, 9 > 8, 7 > 3, 7 > 5, 8 > 6.

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

Строим кучу из массива — после этого максимальный элемент окажется в корне (A[0])
Меняем корень (максимум) с последним элементом — теперь максимум на своём месте
Восстанавливаем свойство кучи для оставшейся части (без последнего элемента)
Повторяем шаги 2–3, пока массив не отсортирован

Разбор

Восстановление свойства кучи (heapify)

Функция heapify проверяет узел и его потомков, и если нужно — «просеивает» элемент вниз:

алг heapify(цел n, цел таб A[0:n-1], цел i)
нач
    цел largest, left, right, tmp
    largest := i
    left := 2 * i + 1
    right := 2 * i + 2

    если (left < n) и (A[left] > A[largest]) то
        largest := left
    все
    если (right < n) и (A[right] > A[largest]) то
        largest := right
    все

    если largest <> i то
        tmp := A[i]
        A[i] := A[largest]
        A[largest] := tmp
        heapify(n, A, largest)
    все
кон

Сравниваем узел i с его левым и правым потомком
Находим наибольший из трёх
Если наибольший — не сам узел, меняем их местами и рекурсивно восстанавливаем поддерево

Основной алгоритм

алг heapsort(цел n, цел таб A[0:n-1])
нач
    цел i, tmp

    | Шаг 1: строим max-heap снизу вверх
    нц для i от div(n - 1, 2) до 0 шаг -1
        heapify(n, A, i)
    кц

    | Шаг 2: извлекаем максимумы
    нц для i от n - 1 до 1 шаг -1
        tmp := A[0]
        A[0] := A[i]
        A[i] := tmp
        heapify(i, A, 0)
    кц
кон

Построение кучи: вызываем heapify для каждого узла снизу вверх (начиная с div(n-1, 2) — последний узел, у которого есть потомки)
Извлечение: меняем A[0] (максимум) с последним элементом A[i], затем восстанавливаем кучу размером i (уменьшенную на 1)

Сложность: $O(n \log n)$ в любом случае. Не требует дополнительной памяти (сортирует «на месте»).

Полная программа

алг main(цел n)
нач
    если n <= 0 то
        вывод "Размер массива должен быть положительным", нс
        выход
    все

    цел таб A[0:n-1]
    заполнить_случайными(n, A)

    вывод "Исходный массив:", нс
    печать_массива(n, A)

    heapsort(n, A)

    вывод "Отсортированный массив:", нс
    печать_массива(n, A)
кон

алг heapify(цел n, цел таб A[0:n-1], цел i)
нач
    цел largest, left, right, tmp
    largest := i
    left := 2 * i + 1
    right := 2 * i + 2

    если (left < n) и (A[left] > A[largest]) то
        largest := left
    все
    если (right < n) и (A[right] > A[largest]) то
        largest := right
    все

    если largest <> i то
        tmp := A[i]
        A[i] := A[largest]
        A[largest] := tmp
        heapify(n, A, largest)
    все
кон

алг heapsort(цел n, цел таб A[0:n-1])
нач
    цел i, tmp

    нц для i от div(n - 1, 2) до 0 шаг -1
        heapify(n, A, i)
    кц

    нц для i от n - 1 до 1 шаг -1
        tmp := A[0]
        A[0] := A[i]
        A[i] := tmp
        heapify(i, A, 0)
    кц
кон

алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        A[i] := irnd(100)
    кц
кон

алг печать_массива(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        вывод A[i], " "
    кц
    вывод нс
кон

▶ Запустить пример