Где применяется
1. Задача
Мимо идёт поток событий: поисковые запросы, ошибки из логов, очки игроков. Тебе нужны 10 наибольших значений. Остальные можно выбросить, а порядок внутри десятки неважен.
Первое, что приходит в голову: собрать всё, отсортировать и взять 10 первых. Это работает, пока данные помещаются в память. Но сортировать миллиард строк ради 10 из них расточительно. А живой поток целиком в памяти и вовсе не удержать.
Тебе в каждый момент нужны только 10 значений. Храни эти 10, а каждое новое значение пусть пробует занять место одного из них. Маленькая куча (heap) делает ровно это.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- всегда нужен текущий минимум/максимум
- k наименьших/наибольших элементов
- слияние k отсортированных списков
- текущая медиана, пока элементы прибывают
- очередь с приоритетом / самое срочное следующим
Похоже, но не то
- Быстрая сортировка (merge / quick) (Fast sort (merge / quick))
Сортировка один раз даёт полный порядок. Куча отдаёт голову много раз, пока данные ещё идут.
- Двоичное дерево поиска (Binary search tree)
Дерево поиска упорядочивает каждую пару узлов. Куча обещает только корень.
- Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min))
Дек умеет выбросить только что устаревший элемент. У кучи дешёвого способа для этого нет.
- Алгоритм Дейкстры (Dijkstra's algorithm)
Дейкстра это самый известный потребитель кучи. Эта страница про сам контейнер.
n до 1e6 даёт O(log n) на вставку или снятие. Чтение вершины стоит O(1).
На LeetCode
Задачи, где нужны k наибольших, k самых частых или k-й по величине элемент. Держи мин-кучу размером не больше k, её корень будет самым слабым из оставленных, а цена O(n log k).
Ограниченная мин-куча из урока живёт между вызовами, а ответ лежит в корне.
Запусти topK с этим k и верни корень вместо всей кучи.
Посчитай частоты словарём, потом держи k наибольших в ограниченной мин-куче.
То же самое, только компаратор при равных частотах решает по алфавиту.