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

Сортировка выбором делает ровно одно: $n$ раз достаёт минимум из оставшихся. Каждый раз она ищет его проходом, за $O(n)$, — отсюда и квадрат.

Вопрос: а если бы минимум доставался быстро? Тогда та же сортировка стала бы $O(n \log n)$, не изменившись ни в одной строчке идеи. Структура, которая это умеет, называется кучей.

Куча — это массив

Кучу удобно представлять деревом, но хранится она обычным массивом. Элемент с индексом $i$ имеет детей $2i+1$ и $2i+2$, а родителя — $\lfloor (i-1)/2 \rfloor$.

graph TD
  A["9 · индекс 0"] --> B["7 · индекс 1"]
  A --> C["8 · индекс 2"]
  B --> D["3 · индекс 3"]
  B --> E["5 · индекс 4"]
  C --> F["1 · индекс 5"]

Инвариант кучи: родитель не меньше своих детей (такая куча называется max-кучей; для минимума знак меняется на обратный). Никакого порядка между братьями не требуется — это не отсортированный массив, а гораздо более слабое условие. Тем оно и дёшево.

Из инварианта сразу следует: максимум лежит в корне, то есть в a[0].

Просеивание

Единственная операция, которая нужна: элемент оказался меньше своих детей — надо опустить его на место.

Меняем его с бо́льшим из детей и повторяем, пока не окажется, что дети меньше или что детей нет. Глубина дерева — $\log_2 n$, значит просеивание стоит $O(\log n)$.

void sift_down(vector<int>& a, int i, int size) {
    while (true) {
        int big = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < size && a[l] > a[big]) big = l;
        if (r < size && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(a[i], a[big]);
        i = big;
    }
}

Построение кучи стоит O(n), а не O(n log n)

Наивно: вставить $n$ элементов по одному, каждая вставка $O(\log n)$, итого $O(n \log n)$.

Но есть способ лучше. Пройдём по массиву с конца и просеем каждый элемент. Листья просеивать не надо — у них нет детей, — поэтому начинаем с середины:

for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n);

Кажется, что это те же $n$ просеиваний по $\log n$. Но глубина у элементов разная. Половина элементов — листья, им просеивание стоит ноль. Четверти надо опуститься на один уровень, восьмой части — на два, и так далее. Складываем:

$$\sum_{k \ge 1} \frac{n}{2^{k+1}} \cdot k \;=\; \frac{n}{2} \sum_{k \ge 1} \frac{k}{2^{k}} \;=\; n$$

Сумма $\sum k/2^k$ равна двум — обычная сходящаяся прогрессия. Построение кучи линейно.

Это тот же приём, что и в поиске $k$-й статистики: работа на уровнях убывает геометрически, и всё вместе сходится к константе, помноженной на $n$.

Сама сортировка

Строим max-кучу. Максимум лежит в корне — меняем его с последним элементом и считаем, что массив стал на единицу короче. Корень нарушил инвариант, просеиваем его. Повторяем.

void heap_sort(vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n);
    for (int size = n; size > 1; size--) {
        swap(a[0], a[size - 1]);
        sift_down(a, 0, size - 1);
    }
}

Отсортированная часть растёт справа, куча ужимается слева. Дополнительной памяти не нужно совсем.

Чем она хороша и чем плоха

	Пирамидальная	Слиянием	Быстрая
Худший случай	$O(n \log n)$	$O(n \log n)$	$O(n^2)$
Дополнительная память	$O(1)$	$O(n)$	$O(\log n)$ на стек
Устойчивость	нет	да	нет
Скорость на практике	ниже всех	средняя	выше всех

Гарантия в худшем случае и отсутствие дополнительной памяти — сочетание, которого нет больше ни у кого. Плата — константа: куча прыгает по массиву большими шагами, и процессорный кеш этого не любит.

Поэтому в чистом виде её пишут редко, зато она стоит внутри std::sort как страховка: если быстрая сортировка ушла в слишком глубокую рекурсию, библиотека переключается на пирамидальную и тем самым закрывает худший случай.

Куча полезна и без сортировки

Сортировка — не главное её применение. Куча нужна там, где на каждом шаге требуется минимум из меняющегося набора: алгоритм Дейкстры, слияние многих списков, планировщики задач.

Вспомните задачу про сто наибольших чисел из статьи про квадратичные сортировки. Куча решает её напрямую: держим min-кучу из ста элементов, каждое новое число сравниваем с корнем и, если оно больше, заменяем корень и просеиваем. Получается $O(n \log 100)$.

В C++ это priority_queue, в Python — модуль heapq:

import heapq

# сто наибольших: держим кучу из ста наименьших среди просмотренных
best = []
for value in numbers:
    if len(best) < 100:
        heapq.heappush(best, value)
    elif value > best[0]:
        heapq.heapreplace(best, value)

Или готовым heapq.nlargest(100, numbers) — внутри ровно это и происходит.