Двоичная куча

TL;DR

Двоичная куча (binary heap; синоним — «бинарная пирамида») — почти полное двоичное дерево, в котором ключ каждого узла не меньше ключей детей (max-куча), упакованное в обычный массив без указателей. Родитель и дети находятся по формулам [math]\displaystyle{ \lfloor i/2\rfloor }[/math], [math]\displaystyle{ 2i }[/math], [math]\displaystyle{ 2i+1 }[/math], поэтому структура занимает ровно [math]\displaystyle{ n }[/math] ячеек и не требует дополнительной памяти. Куча даёт очередь с приоритетом: чтение максимума за [math]\displaystyle{ O(1) }[/math], вставка и извлечение за [math]\displaystyle{ O(\log n) }[/math], а построение из готового массива — за [math]\displaystyle{ O(n) }[/math]. На её основе работают пирамидальная сортировка за [math]\displaystyle{ O(n\log n) }[/math] на месте, алгоритмы Дейкстры и Прима, коды Хаффмана, слияние [math]\displaystyle{ k }[/math] списков и поддержание медианы.

Свойство	Значение
Класс	Двоичное дерево (почти полное), упакованное в массив; реализация очередь с приоритетом
Изобретение	Дж. Уильямс, 1964 (heapsort и куча как структура); Р. Флойд, 1964 (линейное построение) [3][4]
Чтение максимума	[math]\displaystyle{ O(1) }[/math]
Вставка (худший / ожидаемая)	[math]\displaystyle{ O(\log n) }[/math] / [math]\displaystyle{ O(1) }[/math] для случайных данных
Извлечение максимума (худший)	[math]\displaystyle{ O(\log n) }[/math]
Построение из массива	[math]\displaystyle{ O(n) }[/math] (Флойд), не [math]\displaystyle{ O(n\log n) }[/math]
Сортировка на месте	[math]\displaystyle{ O(n\log n) }[/math] времени, [math]\displaystyle{ O(1) }[/math] памяти, неустойчивая
Память	[math]\displaystyle{ n }[/math] ячеек массива; никаких указателей
Упорядоченность	Частичная: максимум в корне, полного порядка нет
Стабильность	Неприменима (куча — не сортировка); heapsort неустойчив
Альтернативы	d-арная куча, биномиальная куча, фибоначчиева куча, splay-дерево, сбалансированное BST, отсортированный массив
Где встречается	heapq (Python), std::priority_queue (C++), java.util.PriorityQueue, Дейкстра/Прим, Хаффман, k-way merge, top-k, медиана

Определения

Почти полное двоичное дерево (nearly complete binary tree) — двоичное дерево, в котором все уровни, кроме, возможно, последнего, заполнены полностью, а последний заполняется слева направо без пропусков. Именно это позволяет упаковать дерево в массив без пустых ячеек.

Двоичная куча (binary heap) — почти полное двоичное дерево, удовлетворяющее свойству кучи: для каждого узла, кроме корня, ключ родителя не меньше ключа узла:

[math]\displaystyle{ \text{key}[\text{parent}(i)] \;\ge\; \text{key}[i]. }[/math]

Такая куча называется max-кучей (максимум в корне). Если знак заменить на обратный ([math]\displaystyle{ \text{key}[\text{parent}(i)] \le \text{key}[i] }[/math]), получается min-куча (минимум в корне). Все рассуждения симметричны; ниже по умолчанию max-куча (как в пирамидальной сортировке).

Массивное представление. Куча хранится в массиве [math]\displaystyle{ A[1..n] }[/math] (нумерация с 1): узел с индексом [math]\displaystyle{ i }[/math] имеет родителя [math]\displaystyle{ \text{parent}(i) = \lfloor i/2 \rfloor }[/math] и детей [math]\displaystyle{ \text{left}(i) = 2i }[/math], [math]\displaystyle{ \text{right}(i) = 2i+1 }[/math]. Дети существуют, только если соответствующая формула не превосходит [math]\displaystyle{ n }[/math]. При нумерации с 0: [math]\displaystyle{ \text{parent}(i) = \lfloor (i-1)/2 \rfloor }[/math], [math]\displaystyle{ \text{left}(i)=2i+1 }[/math], [math]\displaystyle{ \text{right}(i)=2i+2 }[/math].

Высота кучи — высота дерева, равная [math]\displaystyle{ \lfloor \log_2 n \rfloor }[/math] (число рёбер от корня до листа). heap-size — число элементов в куче; может быть меньше длины массива, если часть массива уже отсортирована (как в heapsort).

Мотивация и интуиция

Многие задачи сводятся к повторяющемуся вопросу «дай текущий минимум (или максимум) и добавь/ удали элемент»: планировщик выбирает ближайшую по времени задачу, Дейкстра — ближайшую непомеченную вершину, кодек — два самых редких символа. Хранить всё в обычном массиве и каждый раз искать минимум линейно — [math]\displaystyle{ O(n) }[/math] на запрос; поддерживать полностью отсортированный массив — [math]\displaystyle{ O(n) }[/math] на вставку. Оба варианта плохи при больших [math]\displaystyle{ n }[/math].

Куча даёт компромисс. Достаточно, чтобы максимум был в корне, а не полный порядок: тогда чтение максимума мгновенно ([math]\displaystyle{ O(1) }[/math]), а после изменения одного элемента нарушение локально и лечится спуском или подъёмом по одному пути длиной не более высоты дерева, то есть [math]\displaystyle{ O(\log n) }[/math]. При этом полный порядок нигде не поддерживается — экономия и есть источник эффективности.

Ключевая идея: почти полная форма дерева снимает необходимость в указателях (связи вычисляются из индексов), а свойство кучи делает нарушения локальными (правка одного узла затрагивает только путь до корня или до листа).

Устройство

Двоичная куча — это массив [math]\displaystyle{ A }[/math] и две вещи поверх него (рис. 1):

• Форма: элементы заполняют уровни дерева слева направо, поэтому дерево представимо массивом без пропусков. Число элементов на каждом уровне (кроме последнего) ровно удваивается.
• Свойство кучи: [math]\displaystyle{ \text{key}[\text{parent}(i)] \ge \text{key}[i] }[/math].

Из свойства кучи следует, что максимум всегда в корне ([math]\displaystyle{ A[1] }[/math]), но никакой другой порядок не гарантирован: второй по величине элемент — обязательно один из двух детей корня, [math]\displaystyle{ k }[/math]-й по величине может лежать где угодно в нижних уровнях. Полного упорядочивания нет.

Форма дерева важна для сложности: высота почти полного дерева равна [math]\displaystyle{ \lfloor \log_2 n \rfloor }[/math], поэтому любой путь от листа к корню содержит не более [math]\displaystyle{ \lfloor \log_2 n \rfloor }[/math] шагов; кроме того, листьев около половины, а узлов большой высоты мало — именно этот факт делает построение кучи линейным (см. раздел «Корректность и оценка сложности»).

Рис. 1. Одна и та же max-куча как дерево и как массив [math]\displaystyle{ A[1..7] }[/math]. Максимум 16 — в корне; связи вычисляются по индексам, отдельные указатели не нужны.

Операции и алгоритмы

Операция: просеивание вниз (Max-Heapify)

Идея. Если узел меньше большего из своих детей, свойство кучи нарушено только в этом месте. Меняем узел с большим ребёнком: больший поднимается, узел опускается, — и повторяем в поддереве, куда он попал. Нарушение «стекает» вниз по одному пути.

Пошаговое описание (максимизирующее просеивание).

1. Среди узла [math]\displaystyle{ i }[/math] и его детей найти индекс наибольшего ключа (largest).
2. Если largest [math]\displaystyle{ \ne i }[/math] — обменять [math]\displaystyle{ A[i] }[/math] и [math]\displaystyle{ A[\text{largest}] }[/math].
3. Продолжить просеивание из позиции largest.

Инвариант. Перед обработкой позиции [math]\displaystyle{ i }[/math] поддеревья обоих детей [math]\displaystyle{ i }[/math] уже являются кучами. После обмена единственное возможное нарушение — в позиции largest.

Псевдокод.

Алгоритм Max-Heapify(A, i)
Вход:  A — массив; i — индекс узла; поддеревья детей i — уже кучи
Выход: поддерево с корнем i стало max-кучей
Инвариант: единственное возможное нарушение свойства кучи — в текущей позиции i

1  l ← 2i
2  r ← 2i + 1
3  largest ← i
4  if l ≤ heap-size[A] and A[l] > A[largest]
5      largest ← l
6  if r ≤ heap-size[A] and A[r] > A[largest]
7      largest ← r
8  if largest ≠ i
9      swap(A[i], A[largest])
10     Max-Heapify(A, largest)

Сложность: O(log n) времени (глубина пути вниз), O(log n) стека при рекурсии или O(1) в цикле.
Корректность: индукция по высоте поддерева i. Обмен ставит на место i максимум тройки,
после чего нарушение может остаться только в поддереве largest, где инвариант
восстанавливается рекурсивным вызовом.

Пример. Узел [math]\displaystyle{ A[i]=4 }[/math] с детьми [math]\displaystyle{ 14 }[/math] и [math]\displaystyle{ 7 }[/math]: больший ребёнок 14 > 4, меняем их. Результат — узел 14 с детьми 4 и 7 (рис. 2).

Крайние случаи. Узел-лист (нет детей) — обменов нет. Один ребёнок — только у последнего внутреннего узла [math]\displaystyle{ i=n/2 }[/math] при чётном [math]\displaystyle{ n }[/math]: сравниваем с ним. Дубликаты не мешают: сравнения строгие.

Рис. 2. Max-Heapify: узел 4 меньше большего ребёнка 14, выполняется обмен; узел 4 — лист, поэтому на нём просеивание заканчивается. Дерево и массив показывают одно состояние.

Операция: вставка (Max-Heap-Insert)

Идея. Новый элемент добавляется в конец массива (это сохраняет форму дерева), после чего просеивается вверх: пока он больше родителя, меняется с ним местами. Нарушение поднимается к корню.

Пошаговое описание.

1. Увеличить heap-size и положить ключ в последнюю ячейку.
2. Пока ключ больше родителя — обменять с родителем и подняться на уровень выше.
3. Как только родитель не меньше ключа или достигнут корень — остановиться.

Инвариант. До каждой итерации свойство кучи выполнено всюду, кроме, возможно, позиции текущего элемента; все остальные узлы уже корректны.

Псевдокод.

Алгоритм Max-Heap-Insert(A, key)
Вход:  A — max-куча; key — добавляемый ключ
Выход: куча содержит key, свойство кучи восстановлено
1  heap-size[A] ← heap-size[A] + 1
2  A[heap-size[A]] ← key
3  i ← heap-size[A]
4  while i > 1 and A[parent(i)] < A[i]
5      swap(A[i], A[parent(i)])
6      i ← parent(i)

Сложность: O(log n) времени, O(1) памяти. Для случайных вставок ожидаемое число обменов константно (в среднем O(1)).

Корректность: обмен с родителем восстанавливает свойство на новом месте, а нарушение может остаться только выше; цикл завершается, когда родитель не меньше ключа.

Пример. В массив [math]\displaystyle{ [16,14,10,8,7,9,3] }[/math] добавляем 15 (позиция 8). [math]\displaystyle{ 15 \gt A[4]=8 }[/math] — обмен; [math]\displaystyle{ 15 \gt A[2]=14 }[/math] — обмен; [math]\displaystyle{ A[1]=16 \ge 15 }[/math] — стоп. Результат [math]\displaystyle{ [16,15,10,14,7,9,3,8] }[/math] (рис. 3).

Крайние случаи. Вставка в пустую кучу — сразу корень. Если новый ключ не больше своего родителя (например, при вставке минимума) — достаточно одного сравнения.

Рис. 3. Вставка 15: элемент кладётся в конец и поднимается, пока не станет не больше родителя. Подъём идёт по одному пути — не более [math]\displaystyle{ \lfloor\log_2 n\rfloor }[/math] обменов.

Операция: извлечение максимума (Extract-Max)

Идея. Максимум — в корне. Забираем его, ставим на место корня последний элемент (форма сохраняется, размер уменьшается на 1) и просеиваем корень вниз.

Пошаговое описание.

1. Запомнить [math]\displaystyle{ A[1] }[/math] (результат).
2. Переместить последний элемент в корень, уменьшить heap-size.
3. Выполнить Max-Heapify(A, 1).

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

Псевдокод.

Алгоритм Heap-Extract-Max(A)
Вход:  A — max-куча, heap-size[A] ≥ 1
Выход: максимум A[1]; куча без этого элемента
1  if heap-size[A] < 1
2      error "куча пуста"
3  max ← A[1]
4  A[1] ← A[heap-size[A]]
5  heap-size[A] ← heap-size[A] − 1
6  if heap-size[A] ≥ 1
7      Max-Heapify(A, 1)
8  return max

Сложность: O(log n) времени, O(1) памяти.

Корректность: поддеревья корня — кучи (инвариант), поэтому Max-Heapify восстанавливает свойство во всём дереве.

Крайние случаи. Единственный элемент: после уменьшения размера просеивать нечего (строка 6). Пустая куча — ошибка.

Операции: чтение максимума и изменение ключа

Peek возвращает [math]\displaystyle{ A[1] }[/math] за [math]\displaystyle{ O(1) }[/math] и ничего не меняет.

Increase-Key([math]\displaystyle{ A, i, key) }[/math] (увеличение ключа) заменяет [math]\displaystyle{ A[i] }[/math] на большее значение и просеивает узел вверх — как при вставке. Требуется, чтобы новый ключ не был меньше текущего.

Пошаговое описание.

1. Проверить, что новый ключ не меньше текущего; иначе — ошибка.
2. Записать новый ключ в [math]\displaystyle{ A[i] }[/math].
3. Пока ключ больше родителя — обменять с родителем и подняться на уровень выше.
4. Остановиться, когда родитель не меньше ключа или достигнут корень.

Инвариант. До каждой итерации свойство кучи выполнено всюду, кроме, возможно, позиции [math]\displaystyle{ i }[/math]; все остальные узлы корректны.

Псевдокод.

Алгоритм Heap-Increase-Key(A, i, key)
Вход:  A — max-куча; i — индекс узла; key ≥ A[i] — новое значение ключа
Выход: A[i] = key, свойство кучи восстановлено
Инвариант: свойство кучи нарушено только в позиции i
1  if key < A[i]
2      error "новый ключ меньше текущего"
3  A[i] ← key
4  while i > 1 and A[parent(i)] < A[i]
5      swap(A[i], A[parent(i)])
6      i ← parent(i)

Сложность: O(log n) времени, O(1) памяти.

Корректность: ключ поднимается по одному пути, пока родитель меньше; вне этого пути ничего не менялось.

Пример. В куче [math]\displaystyle{ [16,14,10,8,7,9,3] }[/math] увеличим [math]\displaystyle{ A[5] }[/math] с 7 до 15: [math]\displaystyle{ 15 \gt A[2]=14 }[/math] — обмен; [math]\displaystyle{ A[1]=16 \ge 15 }[/math] — стоп. Результат [math]\displaystyle{ [16,15,10,8,14,9,3] }[/math].

Крайние случаи. Новый ключ равен текущему — обменов нет. Увеличение ключа корня — сразу стоп. Попытка уменьшить ключ через increase-key — ошибка: для этого нужен Decrease-Key.

Decrease-Key (уменьшение ключа) аналогично просеивает узел вниз: [math]\displaystyle{ O(\log n) }[/math]. Именно increase-key для max-кучи (или decrease-key для min-кучи) нужен в алгоритмах на графах.

Операция: удаление произвольного элемента

Идея. Зная индекс [math]\displaystyle{ i }[/math], можно удалить элемент, скопировав на его место последний и затем восстановив свойство кучи в нужную сторону.

Пошаговое описание.

1. Записать на место удаляемого элемента последний элемент кучи.
2. Уменьшить heap-size на 1.
3. Если [math]\displaystyle{ i }[/math] всё ещё внутри кучи: при [math]\displaystyle{ A[i] \gt A[\text{parent}(i)] }[/math] просеять узел вверх, иначе — вниз.

Инвариант. После уменьшения размера свойство кучи может нарушаться только в позиции [math]\displaystyle{ i }[/math].

Псевдокод.

Алгоритм Heap-Delete(A, i)
Вход:  A — max-куча; i — индекс удаляемого элемента, 1 ≤ i ≤ heap-size[A]
Выход: элемент A[i] удалён, свойство кучи восстановлено
Инвариант: единственное возможное нарушение свойства кучи — в позиции i
1  A[i] ← A[heap-size[A]]
2  heap-size[A] ← heap-size[A] − 1
3  if i ≤ heap-size[A]
4      if i > 1 and A[i] > A[parent(i)]
5          while i > 1 and A[i] > A[parent(i)]     # просеивание вверх
6              swap(A[i], A[parent(i)])
7              i ← parent(i)
8      else
9          Max-Heapify(A, i)                       # просеивание вниз

Сложность: O(log n) времени, O(1) памяти.

Корректность: на место удалённого встаёт последний элемент; если он больше родителя, нарушение может быть только на пути вверх, иначе — только в поддереве i, где его лечит Max-Heapify.

Пример. Из кучи [math]\displaystyle{ [16,14,10,8,7,9,3] }[/math] удалим [math]\displaystyle{ A[2]=14 }[/math]: на его место встаёт последний элемент 3, размер становится 6. [math]\displaystyle{ 3 \lt A[1]=16 }[/math] — просеиваем вниз: больший ребёнок [math]\displaystyle{ A[4]=8 }[/math], обмен; в позиции 4 детей уже нет — стоп. Результат [math]\displaystyle{ [16,8,10,3,7,9] }[/math].

Крайние случаи. Удаление последнего элемента: после уменьшения размера [math]\displaystyle{ i }[/math] выходит за heap-size, просеивать нечего. Удаление корня сводится к Heap-Extract-Max, но без возврата значения. Удаление единственного элемента — куча становится пустой.

Операция: построение кучи (Build-Max-Heap)

Идея. Не вставлять элементы по одному (это дало бы [math]\displaystyle{ O(n\log n) }[/math]), а просеять вниз все внутренние узлы от середины массива к началу: листья уже являются корректными кучами высоты 0. Как показывает раздел «Корректность и оценка сложности», суммарная стоимость — [math]\displaystyle{ O(n) }[/math].

Пошаговое описание.

1. Установить heap-size равным длине массива.
2. Для [math]\displaystyle{ i }[/math] от [math]\displaystyle{ \lfloor n/2 \rfloor }[/math] вниз до 1 выполнить Max-Heapify(A, i).

Инвариант. Перед итерацией [math]\displaystyle{ i }[/math] каждый узел с индексом больше [math]\displaystyle{ i }[/math] является корнем max-кучи. После Max-Heapify(A, i) узел [math]\displaystyle{ i }[/math] тоже становится корнем max-кучи. По окончании [math]\displaystyle{ i=1 }[/math] — всё дерево является кучей.

Псевдокод.

Алгоритм Build-Max-Heap(A)
Вход:  A — произвольный массив длины n
Выход: A — max-куча
Инвариант: узлы i+1..n — корни max-куч

1  heap-size[A] ← length[A]
2  for i ← ⌊length[A]/2⌋ downto 1
3      Max-Heapify(A, i)

Сложность: O(n) времени (см. раздел «Корректность и оценка сложности»), O(log n) стека или O(1) при итеративной реализации.

Корректность: индукция по убыванию i; листья (i > ⌊n/2⌋) — тривиальные кучи, а Max-Heapify опирается на то, что поддеревья уже кучи.

Пример. Для [math]\displaystyle{ A=[4,1,3,2,16,9,10] }[/math] обработка [math]\displaystyle{ i=3,2,1 }[/math] даёт max-кучу [math]\displaystyle{ [16,4,10,2,1,9,3] }[/math] (рис. 4 и таблица в разделе «Трассировка примера»).

Крайние случаи. [math]\displaystyle{ n \le 1 }[/math] — цикл не выполняется. Отсортированный по возрастанию массив перестраивается за линейное время.

Рис. 4. Build-Max-Heap: проход от [math]\displaystyle{ i=\lfloor n/2\rfloor }[/math] к началу. Синим отмечены позиции, изменившиеся на шаге. Листья не обрабатываются — у них нет детей.

Операция: пирамидальная сортировка (Heapsort)

Идея. Построить max-кучу за [math]\displaystyle{ O(n) }[/math], затем [math]\displaystyle{ n-1 }[/math] раз поменять корень (максимум) с последним элементом кучи, уменьшить heap-size и просеять новый корень вниз. Отсортированный «хвост» массива растёт справа налево.

Пошаговое описание.

1. Build-Max-Heap(A).
2. Для [math]\displaystyle{ i }[/math] от [math]\displaystyle{ n }[/math] вниз до 2: обменять [math]\displaystyle{ A[1] }[/math] и [math]\displaystyle{ A[i] }[/math]; уменьшить heap-size; Max-Heapify(A, 1).

Инвариант. В начале итерации с параметром [math]\displaystyle{ i }[/math] элементы [math]\displaystyle{ A[i+1..n] }[/math] содержат [math]\displaystyle{ n-i }[/math] наибольших ключей в неубывающем порядке, а [math]\displaystyle{ A[1..i] }[/math] — max-кучу с оставшимися элементами.

Псевдокод.

Алгоритм Heapsort(A)
Вход:  A — массив длины n
Выход: A отсортирован по неубыванию
Инвариант: A[i+1..n] — наибольшие ключи по возрастанию; A[1..i] — max-куча

1  Build-Max-Heap(A)
2  for i ← length[A] downto 2
3      swap(A[1], A[i])
4      heap-size[A] ← heap-size[A] − 1
5      Max-Heapify(A, 1)

Сложность: O(n log n) времени в лучшем, среднем и худшем случае; O(1) памяти.

Корректность: корень кучи — максимум из оставшихся, поэтому на позицию i встаёт правильный элемент; инвариант сохраняется.

Свойства. Heapsort работает на месте ([math]\displaystyle{ O(1) }[/math] памяти сверх массива) и имеет гарантированные [math]\displaystyle{ O(n\log n) }[/math] без риска деградации, но неустойчив и на практике обычно проигрывает быстрой сортировке из-за плохой локальности обращений к памяти.

Рис. 5. Heapsort: максимум уходит в конец массива, куча сжимается, отсортированный хвост (зелёный) растёт справа налево.

Реализация структуры на C++

Класс с настраиваемым компаратором: по умолчанию std::less даёт max-кучу, std::greater — min-кучу. Хранится std::vector, индексация с 0. Метод isHeap() проверяет свойство кучи.

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>

template <typename T, typename Compare = std::less<T>>
class BinaryHeap {
    std::vector<T> a_;
    Compare comp_;     // comp_(x, y): x имеет более низкий приоритет, чем y (как в std::priority_queue)

    void siftUp(std::size_t i) {
        while (i > 0) {
            std::size_t p = (i - 1) / 2;
            if (!comp_(a_[p], a_[i])) break;      // родитель не ниже — на месте
            std::swap(a_[i], a_[p]);
            i = p;
        }
    }
    void siftDown(std::size_t i, std::size_t n) {
        while (true) {
            std::size_t l = 2 * i + 1, r = 2 * i + 2, best = i;
            if (l < n && comp_(a_[best], a_[l])) best = l;   // ребёнок приоритетнее
            if (r < n && comp_(a_[best], a_[r])) best = r;
            if (best == i) break;
            std::swap(a_[i], a_[best]);
            i = best;
        }
    }

public:
    BinaryHeap() = default;

    explicit BinaryHeap(std::vector<T> v) : a_(std::move(v)) {   // Build-Heap за O(n)
        for (std::size_t i = a_.size() / 2; i-- > 0; ) siftDown(i, a_.size());
    }

    void push(const T& x) { a_.push_back(x); siftUp(a_.size() - 1); }

    const T& top() const { return a_.front(); }

    T pop() {
        T res = a_.front();
        a_.front() = a_.back();
        a_.pop_back();
        if (!a_.empty()) siftDown(0, a_.size());
        return res;
    }

    std::size_t size() const { return a_.size(); }
    bool empty() const { return a_.empty(); }

    bool isHeap() const {
        for (std::size_t i = 1; i < a_.size(); ++i)
            if (comp_(a_[(i - 1) / 2], a_[i])) return false;   // нарушение: родитель ниже
        return true;
    }
};

namespace detail {
template <typename T, typename Compare>
void siftDownRange(std::vector<T>& a, std::size_t i, std::size_t n, Compare comp) {
    while (true) {
        std::size_t l = 2 * i + 1, r = 2 * i + 2, best = i;
        if (l < n && comp(a[best], a[l])) best = l;
        if (r < n && comp(a[best], a[r])) best = r;
        if (best == i) return;
        std::swap(a[i], a[best]);
        i = best;
    }
}
}  // namespace detail

template <typename T>
void heapSort(std::vector<T>& a) {
    std::size_t n = a.size();
    std::less<T> higher;                                   // max-куча
    for (std::size_t i = n / 2; i-- > 0; )                 // Build-Heap
        detail::siftDownRange(a, i, n, higher);
    for (std::size_t end = n; end > 1; --end) {
        std::swap(a[0], a[end - 1]);
        detail::siftDownRange(a, 0, end - 1, higher);
    }
}

int main() {
    // 1) построение из массива за O(n) и проверка свойства кучи
    std::vector<int> v = {4, 1, 3, 2, 16, 9, 10};
    BinaryHeap<int> h(v);
    assert(h.isHeap());

    // извлечение даёт ключи по убыванию
    std::vector<int> out;
    while (!h.empty()) out.push_back(h.pop());
    assert(out.front() == 16);
    assert(std::is_sorted(out.rbegin(), out.rend()));

    // 2) min-куча через std::greater
    BinaryHeap<int, std::greater<int>> mn;
    for (int x : {5, 3, 8, 1, 9, 2}) mn.push(x);
    assert(mn.top() == 1);
    assert(mn.isHeap());

    // 3) сортировка на месте
    std::vector<int> w = {5, 3, 8, 1, 9, 2, 7, 4, 6, 0};
    heapSort(w);
    assert(std::is_sorted(w.begin(), w.end()));

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

• В стандартной библиотеке C++ та же структура доступна через std::priority_queue<T> (max-куча), std::priority_queue<T, std::vector<T>, std::greater<T>> (min-куча), а также через алгоритмы std::make_heap, std::push_heap, std::pop_heap над обычным std::vector.
• std::priority_queue не даёт доступа к произвольному элементу и не поддерживает decrease-key; если он нужен (Дейкстра), либо реализуют свою кучу, либо применяют ленивое удаление: кладут повторные записи и отбрасывают устаревшие.
• Для больших индексов дети считаются как 2*i+1, 2*i+2; при использовании знакового типа возможно переполнение — берите std::size_t.
• Копирование контейнера копирует массив целиком и корректно; это дёшево по сравнению с узловыми структурами.

Сводная таблица сложности

Операция	Худший	Средний	Амортизированная	Память
Peek (чтение корня)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Insert	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math] (ожидаемо)	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Extract-Max / Extract-Min	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Increase-Key / Decrease-Key	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Delete (по индексу)	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Build-Heap из массива	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(1) }[/math] итеративно / [math]\displaystyle{ O(\log n) }[/math] стек при рекурсии
Heapsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Merge двух куч	[math]\displaystyle{ \Theta(n) }[/math]	—	—	[math]\displaystyle{ \Theta(n) }[/math]

Примечание. Оценки детерминированы: [math]\displaystyle{ O(\log n) }[/math] — это худший случай, а не средний. Единственная «приятность по вероятности» — ожидаемое [math]\displaystyle{ O(1) }[/math] обменов при случайной вставке (новый элемент обычно остаётся почти на месте). Слияние двух двоичных куч требует перестроения, поэтому [math]\displaystyle{ \Theta(n) }[/math]; для частых слияний используют биномиальные и фибоначчиевы кучи.

Трассировка примера

Построим max-кучу из [math]\displaystyle{ A=[4,1,3,2,16,9,10] }[/math] ([math]\displaystyle{ n=7 }[/math], начинаем с [math]\displaystyle{ i=\lfloor 7/2\rfloor=3 }[/math]).

i	До обработки	Действие	После
—	[4, 1, 3, 2, 16, 9, 10]	исходный массив	[4, 1, 3, 2, 16, 9, 10]
3	[4, 1, 3, 2, 16, 9, 10]	3 < 10 → swap(A[3], A[7])	[4, 1, 10, 2, 16, 9, 3]
2	[4, 1, 10, 2, 16, 9, 3]	A[2]=1 < 16, больший ребёнок A[5]=16 (а не A[4]=2) → swap(A[2], A[5])	[4, 16, 10, 2, 1, 9, 3]
1	[4, 16, 10, 2, 1, 9, 3]	4 < 16 → swap(A[1], A[2]); затем 4 ≥ max(A[4], A[5]) = 2 — стоп	[16, 4, 10, 2, 1, 9, 3]

Итог: [math]\displaystyle{ [16, 4, 10, 2, 1, 9, 3] }[/math] — max-куча. Проверки: [math]\displaystyle{ 16 \ge \{4,10\} }[/math], [math]\displaystyle{ 4 \ge \{2,1\} }[/math], [math]\displaystyle{ 10 \ge \{9,3\} }[/math].

Далее heapsort (рис. 5): swap корня с последним и просеивание: [math]\displaystyle{ [16,4,10,2,1,9,3] \to [10,4,9,2,1,3 \mid 16] \to [9,4,3,2,1 \mid 10,16] \to [4,2,3,1 \mid 9,10,16] \to \dots \to [1,2,3,4,9,10,16] }[/math]. Алгоритм выполняет [math]\displaystyle{ n-1 }[/math] извлечений, каждое за [math]\displaystyle{ O(\log n) }[/math].

Корректность и оценка сложности

Лемма 1 (корректность Max-Heapify). Если поддеревья детей узла [math]\displaystyle{ i }[/math] — max-кучи, то после Max-Heapify(A, i) поддерево с корнем [math]\displaystyle{ i }[/math] — тоже max-куча.

Доказательство. Индукция по высоте поддерева. В базовом случае (лист) доказывать нечего. Пусть узел [math]\displaystyle{ i }[/math] обменялся с ребёнком [math]\displaystyle{ \text{largest} }[/math]. На новой позиции [math]\displaystyle{ i }[/math] стоит наибольший ключ среди трёх узлов, поэтому свойство выполнено для [math]\displaystyle{ i }[/math] и его детей; в поддереве второго ребёнка ничего не менялось, а поддерево [math]\displaystyle{ \text{largest} }[/math] отличается от прежнего лишь тем, что его корень получил меньший ключ, — там применимо индуктивное предположение. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (корректность Build-Max-Heap). После выполнения Build-Max-Heap(A) массив [math]\displaystyle{ A }[/math] является max-кучей.

Доказательство. Инвариант: перед итерацией [math]\displaystyle{ i }[/math] каждый узел с индексом [math]\displaystyle{ \gt i }[/math] — корень max-кучи. База: листья [math]\displaystyle{ i \gt \lfloor n/2\rfloor }[/math] кучами являются. Шаг: поддеревья детей узла [math]\displaystyle{ i }[/math] имеют корни с индексами [math]\displaystyle{ 2i, 2i+1 \gt i }[/math], то есть по инварианту это кучи; по лемме 1 Max-Heapify(A, i) делает корнем кучи и узел [math]\displaystyle{ i }[/math]. При [math]\displaystyle{ i=1 }[/math] вся структура — куча. [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (линейное построение). Build-Max-Heap работает за [math]\displaystyle{ O(n) }[/math].

Доказательство. Узел высоты [math]\displaystyle{ h }[/math] просеивается не более чем за [math]\displaystyle{ O(h) }[/math] шагов. В почти полном дереве число узлов высоты [math]\displaystyle{ h }[/math] не превосходит [math]\displaystyle{ \lceil n/2^{h+1}\rceil }[/math]. Поэтому

[math]\displaystyle{ T(n) \;\le\; \sum_{h=0}^{\lfloor\log_2 n\rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil\!\!\cdot O(h) \;=\; O\!\left(n \sum_{h\ge 0} \frac{h}{2^{h+1}}\right) \;=\; O(n), }[/math]

так как ряд [math]\displaystyle{ \sum_{h\ge 0} h/2^{h+1} = 1 }[/math] (см. рис. 6). [math]\displaystyle{ \blacksquare }[/math]

Следствия. Insert, Extract-Max, Increase-Key, Delete проходят один путь длины не более [math]\displaystyle{ \lfloor\log_2 n\rfloor }[/math]: [math]\displaystyle{ O(\log n) }[/math]. Heapsort = [math]\displaystyle{ O(n) }[/math] на построение плюс [math]\displaystyle{ n-1 }[/math] извлечение по [math]\displaystyle{ O(\log n) }[/math]: [math]\displaystyle{ O(n\log n) }[/math], причём и в худшем случае.

Нижняя граница. Для структуры, работающей в модели сравнений, последовательность из [math]\displaystyle{ n }[/math] вставок и [math]\displaystyle{ n }[/math] извлечений требует [math]\displaystyle{ \Omega(n\log n) }[/math] сравнений, то есть в среднем [math]\displaystyle{ \Omega(\log n) }[/math] на операцию. Иначе говоря, [math]\displaystyle{ O(\log n) }[/math] двоичной кучи для извлечения асимптотически оптимальна с точностью до константы (улучшение возможно лишь в амортизированных границах и для decrease-key, как в фибоначчиевых кучах).

Рис. 6. Число узлов высоты [math]\displaystyle{ h }[/math] не превосходит [math]\displaystyle{ \lceil n/2^{h+1}\rceil }[/math], а каждый стоит [math]\displaystyle{ O(h) }[/math]. Сумма [math]\displaystyle{ \sum h/2^{h+1} }[/math] сходится к 1, поэтому Build-Heap линеен.

Сравнение с альтернативами

Таблица приведена для min-кучи (минимум в корне). Для max-кучи роли Find-Min и Extract-Min играют Find-Max и Extract-Max, а оценки те же.

Структура	Insert	Extract-Min	Decrease-Key	Find-Min	Build	Слияние
Двоичная куча	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]
d-арная куча	[math]\displaystyle{ O(\log_d n) }[/math]	[math]\displaystyle{ O(d\log_d n) }[/math]	[math]\displaystyle{ O(\log_d n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]
Биномиальная куча	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]
Фибоначчиева куча	[math]\displaystyle{ O(1) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Отсортированный массив	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]
Сбалансированное BST	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]

Вердикт. Двоичная куча — «рабочая лошадка»: простая, компактная, с гарантированными [math]\displaystyle{ O(\log n) }[/math], но без быстрого decrease-key и слияния. Для Дейкстры на разреженных графах теоретически нужны фибоначчиевы кучи ([math]\displaystyle{ O(m + n\log n) }[/math] против [math]\displaystyle{ O(m\log n) }[/math]), однако на практике двоичная куча часто быстрее из-за меньших констант и локальности. d-арная куча ускоряет вставку и decrease-key ценой более дорогого извлечения. Для частых слияний берут биномиальные кучи.

Рис. 7. Построение кучи из [math]\displaystyle{ 10^6 }[/math] элементов в худшем случае: [math]\displaystyle{ n }[/math] вставок дают порядок [math]\displaystyle{ n\log_2 n \approx 2\cdot 10^7 }[/math] обменов, алгоритм Флойда — не более [math]\displaystyle{ 2n }[/math]; разница примерно десятикратная.

Где применяется

1. heapq в Python. Модуль реализует min-кучу поверх обычного списка функциями heappush, heappop, heapify ([math]\displaystyle{ O(n) }[/math]); выбрана именно двоичная куча за простоту и компактность в интерпретаторе.
2. std::priority_queue в C++. Контейнер-адаптер по умолчанию — max-куча на std::vector; для min-кучи передают std::greater. Та же структура лежит в основе std::make_heap, std::push_heap, std::pop_heap.
3. java.util.PriorityQueue в Java. Двоичная min-куча; используется в обработке событий, в задачах выбора [math]\displaystyle{ k }[/math]-го элемента и в планировщиках.
4. Алгоритм Дейкстры и Прима. Очередь с приоритетом хранит вершины по текущей оценке расстояния; extract-min даёт ближайшую непомеченную вершину, decrease-key — обновление оценки. На двоичной куче Дейкстра работает за [math]\displaystyle{ O((n+m)\log n) }[/math].
5. Коды Хаффмана. На каждом шаге берутся два символа с наименьшими частотами — классический случай двух extract-min и последующей вставки; куча даёт сжатие за [math]\displaystyle{ O(n\log n) }[/math].
6. Слияние [math]\displaystyle{ k }[/math] отсортированных списков (k-way merge). Куча из первых элементов списков выдаёт минимум за [math]\displaystyle{ O(\log k) }[/math], что даёт [math]\displaystyle{ O(N\log k) }[/math] вместо [math]\displaystyle{ O(Nk) }[/math]; так работает внешняя сортировка.
7. Потоковые top-k и медиана. Для «[math]\displaystyle{ k }[/math] наибольших в потоке» держат min-кучу размера [math]\displaystyle{ k }[/math]; для медианы — две кучи (max для меньшей половины, min для большей) с балансировкой.
8. Планировщики и очереди событий. Задачи упорядочивают по ближайшему времени срабатывания; куча даёт быстрый выбор «ближайшего» и вставку новых таймеров. Некоторые системы предпочитают сбалансированные деревья, когда нужен упорядоченный обход всех элементов.

Историческая справка

• 1964. Дж. У. Дж. Уильямс предложил двоичную кучу и сортировку на её основе (heapsort) в заметке «Algorithm 232: Heapsort» [3]. Сортировка на месте с гарантией [math]\displaystyle{ O(n\log n) }[/math] — редкость для 1964 года.
• 1964. Р. У. Флойд показал, что кучу из массива можно построить за линейное время, простым просеиванием снизу вверх («Algorithm 245: Treesort») [4]. Именно поэтому Build-Heap линеен, а не [math]\displaystyle{ O(n\log n) }[/math].
• 1978. Ж. Вюйемен ввёл биномиальные кучи, поддерживающие быстрое слияние [5].
• 1987. М. Фредман и Р. Тарджан предложили фибоначчиевы кучи с амортизированным [math]\displaystyle{ O(1) }[/math] на decrease-key, что теоретически ускорило Дейкстру и Прима [6].
• Термин heap в названии heapsort и структуры совпадает; не путать с heap — областью динамической памяти.

Типичные ошибки и подводные камни

• Путаница индексации. Формулы [math]\displaystyle{ 2i, 2i+1, \lfloor i/2\rfloor }[/math] — для нумерации с 1; при нумерации с 0 это [math]\displaystyle{ 2i+1, 2i+2, \lfloor(i-1)/2\rfloor }[/math]. Смешение даёт незаметные ошибки.
• Построение кучи вставками. [math]\displaystyle{ n }[/math] вызовов Insert в худшем случае (ключи в порядке убывания) дают [math]\displaystyle{ O(n\log n) }[/math]; Build-Heap — [math]\displaystyle{ O(n) }[/math]. На больших [math]\displaystyle{ n }[/math] разница примерно десятикратная (рис. 7).
• Забыть просеять новый корень. После swap(A[1], A[heap-size]) в Extract-Max без Max-Heapify(A, 1) свойство кучи ломается.
• Порядок операций при decrease-key. Уменьшать ключ и просеивать вниз для max-кучи; для увеличения — вверх. Перепутанное направление оставит нарушение.
• Переполнение индекса. 2*i для большого i в знаковом int переполняется; используйте std::size_t.
• Ожидание полной упорядоченности. Куча даёт только экстремум в корне; [math]\displaystyle{ k }[/math]-й по величине элемент за [math]\displaystyle{ O(1) }[/math] из неё не достать, а обход не даёт сортированной последовательности.
• std::priority_queue без decrease-key. Многие ожидают метод и не находят его; нужен ленивый подход (дубликаты + проверка устаревших записей) или собственная куча.
• Неустойчивость heapsort. Равные ключи могут поменяться местами; если устойчивость важна, heapsort не подходит.
• Изменение ключа «на месте» без sift. Прямая запись в середину массива без increase/ decrease-key нарушает инвариант.

Задачи для практики

1. Проверка кучи. За [math]\displaystyle{ O(n) }[/math] проверьте, что массив — max-куча. Ограничения: [math]\displaystyle{ n\le 10^6 }[/math]. Подсказка: сравните каждый [math]\displaystyle{ A[i] }[/math] с родителем [math]\displaystyle{ A[\lfloor i/2\rfloor] }[/math]. Ответ: один проход.
2. Min-куча из max-кучи. Превратите реализацию в min-кучу, изменив только компаратор. Подсказка: все формулы те же, меняются лишь сравнения.
3. [math]\displaystyle{ k }[/math]-й наименьший элемент. Найдите [math]\displaystyle{ k }[/math]-й наименьший за [math]\displaystyle{ O(n + k\log n) }[/math]. Подсказка: постройте min-кучу и выполните [math]\displaystyle{ k }[/math] извлечений. Ответ: [math]\displaystyle{ O(n + k\log n) }[/math].
4. Слияние [math]\displaystyle{ k }[/math] списков. Слейте [math]\displaystyle{ k }[/math] отсортированных списков суммарной длины [math]\displaystyle{ N }[/math] за [math]\displaystyle{ O(N\log k) }[/math]. Подсказка: куча из текущих голов каждого списка.
5. Потоковый top-k. Для потока чисел держите [math]\displaystyle{ k }[/math] наибольших за [math]\displaystyle{ O(\log k) }[/math] на элемент. Подсказка: min-куча размера [math]\displaystyle{ k }[/math]; вытесняйте корень, если пришёл больший.
6. Медиана двух куч. Поддерживайте медиану потока операциями Insert и GetMedian. Подсказка: max-куча левой половины и min-куча правой; балансируйте размеры.
7. Докажите [math]\displaystyle{ O(n) }[/math] построения. Выведите оценку [math]\displaystyle{ \sum_h h\cdot\lceil n/2^{h+1}\rceil }[/math] и докажите сходимость ряда. Подсказка: [math]\displaystyle{ \sum_{h\ge0} h x^h = x/(1-x)^2 }[/math] при [math]\displaystyle{ x=1/2 }[/math].
8. d-арная куча. Реализуйте кучу с [math]\displaystyle{ d }[/math] детьми и сравните число сравнений с двоичной при [math]\displaystyle{ n=10^6 }[/math]. Подсказка: глубина [math]\displaystyle{ \log_d n }[/math], но выбор минимума среди [math]\displaystyle{ d }[/math] детей стоит [math]\displaystyle{ d }[/math].

Связанные темы

Статьи по ссылкам пока не созданы; все перечисленные темы — план.

• Сортировки (план) — место heapsort среди алгоритмов сортировки.
• Быстрая сортировка (план) — альтернатива heapsort: быстрее в среднем, без гарантии в худшем.
• Пирамидальная сортировка (план) — heapsort подробно: build-heap, sift-down, bottom-up.
• Алгоритм Дейкстры (план) — очередь с приоритетом на графах.
• Алгоритм Прима (план) — минимальное остовное дерево.
• Код Хаффмана (план) — жадное сжатие на куче.
• Биномиальная куча (план) — быстрое слияние за [math]\displaystyle{ O(\log n) }[/math].
• Фибоначчиева куча (план) — амортизированное [math]\displaystyle{ O(1) }[/math] на decrease-key.
• Очередь с приоритетом (план) — абстрактный тип данных.
• Двоичное дерево поиска (план) — полное упорядочивание против частичного.
• Асимптотическая сложность (план) — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 6 «Heapsort», гл. 19 «Fibonacci Heaps».
2. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3 «Sorting by Selection» (heapsort).
3. Williams J. W. J. Algorithm 232: Heapsort // Communications of the ACM. — 1964. — Vol. 7, No. 6. — P. 347–348.
4. Floyd R. W. Algorithm 245: Treesort // Communications of the ACM. — 1964. — Vol. 7, No. 12. — P. 701.
5. Vuillemin J. A Data Structure for Manipulating Priority Queues // Communications of the ACM. — Vol. 21, No. 4. — P. 309–315.
6. Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Journal of the ACM. — 1987. — Vol. 34, No. 3. — P. 596–615.
7. Wikipedia: Binary heap. URL: https://en.wikipedia.org/wiki/Binary_heap.
8. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 2.4 «Priority Queues».