Куча как структура данных: массив и просеивание

Куча (heap) как структура данных отвечает на один очень узкий запрос: «дай самый приоритетный элемент и позволь быстро добавить новый». Она не умеет искать произвольное значение и не хранит элементы отсортированными, зато минимум лежит в ней всегда на одном и том же месте, а вставка и удаление стоят $O(\log n)$. Ниже разбираем классическую бинарную кучу: свойство кучи, укладку дерева в обычный массив, два просеивания и неожиданный факт про построение за линейное время. Калькулятор ниже считает индексы и цену построения для любого размера, так что формулы можно проверять прямо по ходу чтения.

Свойство кучи: что именно упорядочено

Бинарная куча (min-heap) это полное двоичное дерево, в котором для каждого узла выполнено

$a[\text{parent}(i)] \le a[i]$

Полное двоичное дерево означает, что все уровни заполнены целиком, кроме последнего, а последний заполняется слева направо без дыр. Отсюда сразу следует высота $h = \lfloor \log_2 n \rfloor$: дерево из $n$ узлов не может быть глубже, потому что каждый полный уровень удваивает число узлов.

Важно понять, чего свойство кучи НЕ требует. Порядок задан только вдоль путей от корня к листьям. Между братьями, между соседними ветками, между двумя произвольными узлами одного уровня порядка нет никакого. Поэтому куча это частичный, а не полный порядок, и выписанный подряд массив кучи почти никогда не отсортирован. Зато минимум гарантированно лежит в корне: если бы меньший элемент был где-то глубже, на пути от него к корню нашлась бы пара, нарушающая неравенство.

Максимальная куча (max-heap) устроена зеркально: $a[\text{parent}(i)] \ge a[i]$, в корне лежит максимум. Все формулы индексов и оба просеивания у неё те же, меняется только знак сравнения.

Куча в массиве: индексы 2i+1 и 2i+2

Главный практический трюк кучи в том, что дерево нигде не материализуется. Нет ни узлов, ни указателей, ни выделения памяти под них: есть обычный массив $a[0 \dots n-1]$, а дерево живёт в арифметике индексов. При нумерации с нуля

$\text{left}(i) = 2i + 1, \qquad \text{right}(i) = 2i + 2, \qquad \text{parent}(i) = \left\lfloor \frac{i - 1}{2} \right\rfloor$

Работает это ровно потому, что дерево полное: узлы идут по уровням слева направо без пропусков, и позиция в массиве однозначно кодирует позицию в дереве. Уровень узла $i$ равен $\lfloor \log_2 (i+1) \rfloor$, весь уровень $k$ занимает индексы от $2^k - 1$ до $2^{k+1} - 2$.

Из тех же формул получается ещё одно полезное следствие. Узел $i$ имеет детей только если $2i + 1 < n$, то есть внутренние узлы занимают индексы от $0$ до $\lfloor n/2 \rfloor - 1$, а вся вторая половина массива это листья. Половина элементов кучи, таким образом, вообще не требует проверки.

Рассчитать для своей задачи

Если в коде куча вдруг ведёт себя странно, первым делом проверяют именно нумерацию: в учебниках и в академических псевдокодах массив часто нумеруют с единицы, и тогда формулы выглядят как $2i$, $2i+1$ и $\lfloor i/2 \rfloor$. Смешать два соглашения в одном файле это самый быстрый способ получить кучу, которая работает на первых трёх тестах и разваливается на четвёртом.

Sift-up: вставка нового элемента

Вставка не ищет место заранее. Новый ключ кладут в первую свободную ячейку, то есть в $a[n]$, увеличивают размер и запускают просеивание вверх (sift-up, он же swim, он же percolate-up): пока элемент меньше своего родителя, они меняются местами.

siftUp(i):
    while i > 0 and a[i] < a[(i - 1) / 2]:
        swap(a[i], a[(i - 1) / 2])
        i = (i - 1) / 2

Свойство кучи при этом не ломается нигде, кроме одной пары, и каждый обмен чинит именно её, сдвигая проблему на уровень выше. Путь идёт строго по цепочке предков, а их всего $\lfloor \log_2 n \rfloor$, поэтому вставка стоит $O(\log n)$ и ровно столько же сравнений: на каждом уровне сравнение ровно одно.

Рассчитать для своей задачи

Sift-down и извлечение минимума

Извлечение минимума устроено сложнее ровно на одну деталь. Корень это ответ, но просто удалить его нельзя: дерево распадётся на два. Поэтому в корень переносят последний элемент массива, уменьшают размер на единицу и запускают просеивание вниз (sift-down, sink, percolate-down): элемент меняется местами с меньшим из двух детей, пока хотя бы один ребёнок меньше него.

siftDown(i):
    while 2*i + 1 < n:
        j = 2*i + 1
        if j + 1 < n and a[j + 1] < a[j]:
            j = j + 1
        if a[i] <= a[j]:
            break
        swap(a[i], a[j])
        i = j

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

Из этих двух процедур собирается всё остальное: decrease-key меняет значение и делает sift-up, increase-key делает sift-down, delete(i) заменяет элемент последним и запускает то просеивание, которое требуется по знаку сравнения. Чтение минимума (peek) стоит $O(1)$: это просто $a[0]$.

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

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

Достаточно пройти внутренние узлы от последнего к первому, то есть от индекса $\lfloor n/2 \rfloor - 1$ до $0$, и для каждого вызвать sift-down. Листья пропускаются: одиночный узел уже является корректной кучей. К моменту обработки узла $i$ оба его поддерева уже кучи, поэтому одного просеивания хватает.

Оценка стоимости выглядит контринтуитивно, но арифметика простая. Узлов высоты $h$ в куче не больше $\lceil n/2^{h+1} \rceil$, а просеивание такого узла стоит не больше $h$ обменов, поэтому

$\sum_{h=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^{h+1}} \cdot h \;=\; \frac{n}{2} \sum_{h \ge 0} \frac{h}{2^{h}} \;=\; \frac{n}{2} \cdot 2 \;=\; n$

Суть в том, что дорогие просеивания достаются редким узлам. Половина элементов это листья с нулевой стоимостью, четверть просеивается на один уровень, и только один корень проходит всю высоту. В худшем случае число обменов равно в точности $n - s_2(n)$, где $s_2(n)$ это количество единиц в двоичной записи $n$, то есть строго меньше $n$.

Рассчитать для своей задачи

Приоритетная очередь: где куча работает

Куча это стандартная реализация абстрактного типа «приоритетная очередь», и почти всюду, где в алгоритме встречается фраза «взять ближайший или самый дешёвый элемент», внутри стоит именно она. На том же извлечении максимума построена и пирамидальная сортировка: она гоняет кучу по убывающему хвосту массива и получает $O(n\log n)$ в худшем случае.

• Алгоритм Дейкстры на каждом шаге достаёт вершину с минимальной оценкой расстояния: с бинарной кучей это $O((V + E)\log V)$ вместо $O(V^2)$ на массиве.
• Алгоритм Прима выбирает минимальное ребро, ведущее наружу из уже построенной части остова.
• Коды Хаффмана $n$ раз вынимают два самых редких символа и кладут обратно их объединение.
• Задача «top-k из потока»: куча размера $k$ даёт $O(n \log k)$ и постоянную память, что заметно лучше полной сортировки при малом $k$.
• Планировщики задач и дискретно-событийное моделирование: очередь событий по времени наступления.

У бинарной кучи есть ровно одно слабое место: слияние двух куч стоит $O(n)$, потому что массивы приходится сливать и перестраивать. Если операция merge нужна часто, берут биномиальную кучу с её $O(\log n)$ или кучу Фибоначчи с амортизированной константой на insert и decrease-key. За это платят указателями, ссылками на родителей и заметно худшей константой, поэтому на практике бинарная куча на массиве выигрывает почти всегда.

Частые ошибки

• Считать кучу отсортированным массивом. Порядок есть только вдоль путей к корню; массив $[1, 3, 2, 7, 5, 6, 4]$ это корректная куча, хотя четвёрка стоит после шестёрки.
• Смешивать нумерацию с нуля и с единицы. Формулы $2i+1$, $2i+2$ и $2i$, $2i+1$ нельзя использовать в одном коде: ошибка проявляется не сразу и выглядит как случайное нарушение порядка.
• Строить кучу вставками, считая это оптимальным. Проход sift-down от $\lfloor n/2 \rfloor - 1$ к нулю даёт линейное время; наивный цикл вставок даёт логарифмический множитель сверху.
• В sift-down сравнивать только с левым ребёнком. Обмен с бо́льшим из детей ломает свойство кучи для второго ребёнка.
• Искать в куче произвольный элемент за $O(\log n)$. Поиск по значению это полный перебор $O(n)$: для decrease-key по ключу нужен внешний словарь «значение к позиции», который обновляется при каждом обмене.

FAQ

Чем куча отличается от двоичного дерева поиска? Двоичное дерево поиска задаёт полный порядок: левое поддерево меньше узла, правое больше, поэтому поиск любого ключа стоит $O(\log n)$, а обход по возрастанию делается за один проход. Куча задаёт только частичный порядок, зато гарантирует идеальную сбалансированность без всякой балансировки и обходится массивом без указателей. Одна структура отвечает на вопрос «есть ли такой ключ», другая на вопрос «какой ключ минимален».

Почему построение кучи стоит $O(n)$, если высота дерева $\log n$? Потому что высоту проходит не каждый узел. Половина элементов это листья, которые не просеиваются вообще, четверть просеивается на один уровень, восьмая часть на два. Сумма $\sum h \cdot n/2^{h+1}$ сходится к $n$, тогда как при вставке по одному каждый новый элемент действительно может всплыть до корня.

Что такое куча в смысле управления памятью, это то же самое? Нет, совпадение терминов случайное. Куча как структура данных это описанное выше дерево в массиве; куча в смысле памяти (heap) это область динамического выделения, где живут объекты, созданные через new или malloc. Общего у них только слово.

Коротко

Бинарная куча это полное двоичное дерево со свойством «родитель не больше обоих детей», уложенное в обычный массив: дети индекса $i$ лежат на $2i+1$ и $2i+2$, родитель на $\lfloor (i-1)/2 \rfloor$, высота равна $\lfloor \log_2 n \rfloor$. Все операции держатся на двух просеиваниях: sift-up после вставки в конец и sift-down после переноса последнего элемента в корень, обе стоят $O(\log n)$, а чтение минимума $O(1)$. Построение кучи из готового массива проходом по внутренним узлам справа налево стоит $O(n)$ обменов, а не $O(n \log n)$, потому что дорогие просеивания достаются редким узлам. Эта структура и есть стандартная приоритетная очередь; отказываться от неё в пользу биномиальной или Фибоначчиевой имеет смысл только там, где нужен частый merge или дешёвый decrease-key.