Бинарная куча: как устроена, когда нужна и как написать на Python
Elman Huseynov · 2026-09-29
Короткий ответ. Бинарная куча это массив, который ведёт себя как дерево. Корень всегда хранит минимум или максимум. Вставка и удаление стоят O(log n), а взять минимум можно за O(1). Её берут, когда задача просит «k самых» или «следующий по порядку». Ниже устройство, код на Python и типичные ошибки.
Что такое бинарная куча?
Куча это полное двоичное дерево с одним правилом. Каждый родитель не больше своих детей. Такая куча называется min-heap. Если родитель не меньше детей, это max-heap.
Дерево при этом никто не строит из узлов. Оно лежит в обычном массиве. Это главная причина, почему куча быстрая и экономная.
На собеседовании куча почти всегда появляется под именем «очередь с приоритетом». Это одна и та же структура.
kSmallest([5, 1, 8, 3, 9, 2], 3)Храним 3 наименьших числа из [5, 1, 8, 3, 9, 2] в max-куче. В корне самое большое из оставленных, поэтому оно и уходит первым.
Столбики: 40 чисел. Сортировка переставляет их все; куча их только читает, держит свои 5 чисел отдельно и подсвечивает то, которое сейчас рассматривает.
Одна операция: одно сравнение или одно перемещение. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n log n)O(n log k)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Страница паттерна: когда его применять и шаблон на шести языках
Как бинарная куча хранится в массиве?
Корень лежит в позиции 0. Дети элемента i лежат в позициях 2i + 1 и 2i + 2. Родитель элемента i лежит в позиции (i - 1) // 2.
Никаких указателей. Переход к ребёнку это умножение, переход к родителю это деление. Уровни дерева заполняются слева направо без дыр.
| Операция | Время | Что происходит |
|---|---|---|
| Посмотреть минимум | O(1) | Читаем позицию 0 |
| Вставить | O(log n) | Кладём в конец, поднимаем вверх |
| Удалить минимум | O(log n) | Последний в корень, опускаем вниз |
| Построить из массива | O(n) | Опускаем каждый узел с середины к началу |
| Найти произвольный элемент | O(n) | Куча этого не умеет |
По каким словам в задаче узнать кучу?
- «k наибольших», «k ближайших», «k самых частых».
- «Слить k отсортированных списков».
- «Медиана потока» или «текущий минимум при постоянных вставках».
- «Планировщик задач», «следующее событие по времени».
Общий признак один. Данные приходят или меняются, а нужен всё время самый маленький или самый большой. Полная сортировка на каждом шаге стоит O(n log n). Куча делает то же за O(log n).
Как работают подъём и спуск?
- Вставка: новый элемент идёт в конец массива. Пока он меньше родителя, меняем их местами. Это подъём.
- Удаление минимума: корень запоминаем, на его место ставим последний элемент. Пока он больше кого-то из детей, меняем с меньшим ребёнком. Это спуск.
Высота полного дерева равна log n. Подъём и спуск проходят не больше одной ветки. Отсюда O(log n).
Как выглядит вставка на примере?
Возьмём min-heap [1, 3, 2, 7, 5]. Вставляем 0. Он идёт в конец: [1, 3, 2, 7, 5, 0]. Его индекс 5, родитель в позиции 2, там лежит 2.
0 меньше 2, меняем: [1, 3, 0, 7, 5, 2]. Теперь индекс 2, родитель в позиции 0, там лежит 1. 0 меньше 1, меняем ещё раз: [0, 3, 1, 7, 5, 2]. Подъём закончен за два шага.
Удаление минимума идёт в обратную сторону. Снимаем 0, ставим на его место 2, и 2 опускается вниз к своему уровню. На каждом шаге выбираем меньшего ребёнка. Иначе правило кучи нарушится.
Как написать бинарную кучу на Python?
В Python есть модуль heapq. Он работает поверх обычного списка и делает min-heap.
import heapq
nums = [5, 1, 8, 3, 2]
heapq.heapify(nums) # O(n), nums[0] == 1
heapq.heappush(nums, 0) # O(log n)
smallest = heapq.heappop(nums) # 0
# max-heap: храним числа со знаком минус
top = []
for x in [5, 1, 8]:
heapq.heappush(top, -x)
largest = -heapq.heappop(top) # 8
# k наименьших за O(n log k)
def k_smallest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, -x)
if len(heap) > k:
heapq.heappop(heap)
return sorted(-x for x in heap)Приём с минусом стоит запомнить. Второй способ это кортежи вида (приоритет, значение). Кортежи сравниваются по первому полю.
Как решить задачу Kth Largest Element через кучу?
Условие: найти k-й по величине элемент массива. Сортировка даёт O(n log n). Куча даёт O(n log k).
Держим min-heap размера k. Каждый элемент кладём в кучу. Если размер стал k + 1, снимаем минимум. В конце в корне лежит ответ.
Почему это работает. Куча всегда хранит k самых больших из просмотренных. Самый маленький из них и есть k-й по величине.
На каких ошибках ломается решение с кучей?
- Кучу используют как отсортированный список. Отсортирован только корень, остальные элементы лежат в произвольном порядке.
- Забывают про минус для max-heap и получают k наименьших.
- Кладут в кучу несравнимые объекты. Нужен кортеж с числом в первом поле.
- Ищут элемент в куче линейным проходом и считают, что это O(log n).
Как объяснить кучу на собеседовании?
Скажите, что нужен быстрый доступ к минимуму при постоянных вставках. Назовите время операций из таблицы выше. Покажите формулу детей 2i + 1 и 2i + 2.
Потом назовите альтернативу. Сортировка проще, но стоит O(n log n) на каждое изменение. Это и есть довод в пользу кучи.
Тренировать узнавание кучи среди соседних приёмов можно на странице бинарная куча. Общий список приёмов лежит в статье паттерны алгоритмов.
Вопросы и ответы
Чем куча отличается от двоичного дерева поиска?
В дереве поиска слева всё меньше, справа всё больше. В куче только родитель меньше детей. Поэтому куча не умеет искать, зато строится за O(n).
Почему построение кучи стоит O(n), а не O(n log n)?
Половина узлов это листья, их опускать не надо. Чем выше узел, тем их меньше. Сумма всех спусков сходится к линейной.
Когда куча хуже сортировки?
Когда данные не меняются и нужны все элементы по порядку. Тогда одна сортировка проще и быстрее по константе.