Теория

Куча — практическое воплощение приоритетной очереди.

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

Поддерживаемые операции и их сложность

Операция	Сложность
Вставка элемента	O(log n)
Удаление наименьшего элемента	O(log n)
Получение наименьшего элемента	O(1)

Если вместо минимума требуется максимум, используется max-heap; когда нужен минимум — min-heap. Алгоритмические свойства остаются теми же.

Благодаря постоянному времени доступа к текущему минимуму и логарифмическим затратам на обновление структура оказывается чрезвычайно эффективной.

Мини-куча и макс-куча

Куча бывает двух «настроек»:

• Min-heap (мини-куча) — наверху (в корне) всегда самый маленький элемент.
• Max-heap (макс-куча) — наверху всегда самый большой элемент.

И та и другая позволяют за O(1) узнать текущий минимум/максимум, а за O(log n) вставлять новые значения или удалять корень.

Как это выглядит в памяти

Мини-куча:

      4
    /   \
   8     17
  / \   /  \
15 20 42  50

Макс-куча:

      50
    /    \
  42      23
 /  \    /  \
15 20   8    4

---

Классическое устройство: бинарная куча в массиве

На практике большинство языков уже содержат готовый тип данных «куча», поэтому писать её с нуля не приходится. Тем не менее понимание внутренней механики полезно, например, на собеседованиях.

Логика размещения элементов

Бинарная куча хранится в обычном массиве и одновременно представляет собой полное бинарное дерево с инвариантом:

значение_родителя ≤ значение_потомка

Инвариант кучи

Что такое инвариант

Инвариант — это правило, которое остаётся истинным при любых допустимых действиях с объектом.

Можно думать так: *«Что бы мы ни делали, вот это условие не имеет права нарушиться*.

Пример из повседневной жизни

Лифт: сколько бы пассажиров ни входило и ни выходило между этажами, кабина всегда стоит на одной из остановок, а не «застряла посередине шахты». → «Кабина находится ровно на этаже» — инвариант работы лифта.

Инвариант в куче

• Мини-куча: значение_родителя ≤ значение_потомка
• Макс-куча: значение_родителя ≥ значение_потомка

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

Если при вставке новый элемент «ломает» порядок, он поднимается (bubble up) до первого места, где инвариант снова выполняется. Если мы удаляем корень, последний элемент ставится на его место и «просеивается» вниз (bubble down) по тому же правилу. Благодаря этому вставка и удаление остаются логарифмическими, а чтение — мгновенным.

Из этого автоматически следует, что элемент с минимальным значением всегда находится в корне (индекс 0).

Связи между вершинами определяются формулами:

• для узла с индексом i

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

Поддержание инварианта

После вставки нового элемента или удаления корня нарушенный порядок восстанавливается «просеиванием» (bubble up / bubble down). Количество перестановок при этом пропорционально высоте дерева, то есть log n.

Построение за линейное время

Существующий массив можно «перестрясать» в кучу всего за O(n). Реализация нетривиальна, но во многих стандартных библиотеках есть готовая функция heapify.

Почему куча ускоряет алгоритмы

Во множестве задач требуется многократно извлекать текущий минимум (или максимум). Замена наивного поиска (O(n)) на обращение к куче позволяет улучшить время работы алгоритма с O(n²) до O(n log n) — при миллионе элементов это в пятьдесят тысяч раз быстрее.

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

Во многих задачах использование кучи улучшает временную сложность алгоритма с O(n²) до O(n · log n), что даёт колоссальный выигрыш (при n = 1 000 000 это в 50 000 раз быстрее).
Куча — отличный выбор, когда нужно многократно находить максимум или минимум.