Что такое куча (heap) в программировании и зачем она?
Постоянно встречаю слово «куча» и совсем запутался. То говорят про кучу как область памяти, то про какую-то структуру данных heapq в Python. Это одно и то же или разные вещи? И если это структура, то чем она лучше обычного отсортированного списка? Хочу понять, когда её реально применять.
2 ответа
Сразу сниму главную путаницу: это два РАЗНЫХ понятия с одинаковым названием.
- «Куча памяти» (heap memory) — область, где живут динамически выделенные объекты. К нашей теме отношения не имеет.
- Куча как структура данных (binary heap) — про неё и пойдёт речь.
Бинарная куча — это почти полное бинарное дерево, в котором соблюдается инвариант кучи:
- min-heap: родитель всегда ≤ своих детей → в корне минимум.
- max-heap: родитель всегда ≥ детей → в корне максимум.
Важно: куча не полностью отсортирована. Гарантируется только верхушка. Зато за это мы получаем очень дёшево:
- вставка элемента — O(log n);
- извлечение минимума/максимума — O(log n);
- подсмотреть минимум (корень) — O(1).
В Python это модуль heapq (реализует min-heap поверх обычного списка):
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(h[0]) # 1 — минимум, O(1)
print(heapq.heappop(h)) # 1 — извлекаем минимум, O(log n)
print(heapq.heappop(h)) # 3
Чем лучше отсортированного списка? Чтобы держать список отсортированным, каждая вставка стоит O(n) (надо подвинуть элементы). У кучи вставка — O(log n). Если тебе постоянно нужен только минимум/максимум, а не весь порядок — куча выигрывает.
Где применяют:
- Приоритетная очередь — обслуживаем задачи по приоритету.
- Алгоритм Дейкстры — всегда берём ближайшую вершину.
- Top-K элементов — держим кучу размера K, это O(n log K).
Лайфхак для max-heap: heapq минимальная, поэтому клади числа со знаком минус.
Полезный практический приём к ответу выше — для top-K не сортируй весь массив (это O(n log n)). Используй heapq.nlargest / nsmallest:
import heapq
nums = [7, 2, 9, 1, 5, 8]
print(heapq.nlargest(3, nums)) # [9, 8, 7]
Внутри держится куча размера K, поэтому сложность O(n log K), что при маленьком K заметно быстрее полной сортировки. Очень частый паттерн на собеседованиях: «найди K самых больших/частых».
