Куча и приоритетная очередь

Зачем нужна куча

Представь приёмный покой в больнице. Люди приходят в случайном порядке, но врач берёт не того, кто пришёл первым, а того, кому хуже всех. Новые пациенты всё время прибывают. Медсестре нужно быстро делать две вещи:

• добавить нового пациента;
• назвать, кто сейчас самый срочный, и отправить его к врачу.

Это и есть приоритетная очередь. Её почти всегда реализуют через двоичную кучу. Обе операции она делает за O(log n), а подсмотреть минимум позволяет за O(1).

Сравни с другими вариантами:

Структура	Добавить	Достать минимум
Несортированный массив	O(1)	O(n)
Отсортированный массив	O(n)	O(1)
Куча	O(log n)	O(log n)

Что такое двоичная куча

Куча — это почти полное двоичное дерево: все уровни заполнены, только последний может быть заполнен не до конца, и заполняется он слева направо. Для min-кучи действует одно правило: родитель не больше своих детей. Поэтому минимум всегда лежит в корне.

Учти: между братьями порядка нет. В примере 3 стоит левее 2, и это нормально. Куча — не отсортированный массив, она лишь гарантирует, что сверху меньшее.

Дерево, которое живёт в массиве

Указатели для кучи не нужны. Обойди дерево по уровням слева направо и запиши значения подряд. Получится обычный массив:

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

• левый ребёнок: 2*i + 1
• правый ребёнок: 2*i + 2
• родитель: (i - 1) // 2

Проверь на схеме: у узла с индексом 4 (значение 4) родитель равен (4-1)//2 = 1, то есть узлу 3. Сходится.

Вставка: всплытие (sift up)

1. Кладём новый элемент в конец массива. Это первое свободное место на нижнем уровне.
2. Пока он меньше родителя, меняем их местами.

Допустим, вставляем 0. Он встаёт на индекс 7 и сравнивается с 7, потом с 3, потом с 1. С каждым из них он меняется местами и в итоге оказывается в корне. Высота дерева равна log n, поэтому шагов не больше log n.

Извлечение минимума: просеивание (sift down)

1. Запоминаем корень, это и есть ответ.
2. Последний элемент массива переносим в корень, а массив укорачиваем на один.
3. Пока элемент больше хотя бы одного из детей, меняем его с меньшим ребёнком.

Путь опять идёт сверху вниз по высоте дерева, значит это тоже O(log n).

Куча в пяти языках

Язык	Что использовать	По умолчанию
Python	heapq	min-куча
Java	PriorityQueue	min-куча
C++	priority_queue	max-куча
Go	container/heap	нужен свой тип с интерфейсом
JavaScript	встроенной нет	пишем свой класс

Приём top-K: куча размера k

Задача-пример: из потока слов оставить k самых длинных.

Можно отсортировать всё за O(n log n), но есть способ лучше. Держим min-кучу размера k. В её корне лежит «самый слабый из лучших». Каждое новое слово кладём в кучу, а если в ней стало больше k элементов, выкидываем корень. В конце в куче остаются ровно k самых длинных слов.

Идея звучит парадоксально: чтобы найти наибольшие, берём min-кучу. Так мы быстро выгоняем худшего из претендентов.

import heapq

def top_k_longest(words, k):
    heap = []  # min-куча пар (длина, слово)
    for w in words:
        heapq.heappush(heap, (len(w), w))
        if len(heap) > k:
            heapq.heappop(heap)  # выкидываем самое короткое
    return [w for _, w in heap]

Сложность

• вставка и извлечение: O(log n), подсмотреть минимум: O(1);
• top-K: O(n log k) по времени и O(k) по памяти. Если k намного меньше n, это заметно быстрее сортировки. К тому же приём работает на потоке, когда все данные сразу не видны.

Как это звучит на собесе

«Мне нужно многократно доставать минимум из меняющегося набора, поэтому возьму приоритетную очередь на двоичной куче: вставка и извлечение за O(log n). Для k наибольших держу min-кучу размера k: в корне лежит худший из текущих кандидатов, и его легко вытеснить. Итого O(n log k) времени и O(k) памяти».

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

• Перепутать min и max. В C++ куча по умолчанию максимальная, в Python и Java минимальная. Max-кучу в Python делают так: кладут -x.
• Брать max-кучу для top-K наибольших. Тогда придётся хранить все n элементов, а не k.
• Считать кучу отсортированной. Отсортированной её делает только последовательность извлечений, а не обход массива.
• Сравнивать несравнимое. В Python кортеж (приоритет, объект) упадёт при равных приоритетах, если объекты нельзя сравнить. Добавь в середину счётчик: (приоритет, i, объект).
• Ошибиться в индексах. При нумерации с нуля дети лежат на 2i+1 и 2i+2, а не на 2i и 2i+1.

Теперь ты знаешь, как устроена куча изнутри и как пользоваться ею в любом языке. Дальше будет практика, и приём «куча размера k» тебе там точно пригодится.