Где применяется
1. Задача
У тебя есть набор задач, и следующей всегда нужно брать самую срочную. Новые задачи приходят прямо во время работы, поэтому самая срочная задача всё время меняется.
Простое решение: держать список отсортированным. Тогда самая срочная задача всегда первая. Но каждую новую задачу приходится вставлять на её место, а для этого нужен проход по списку. Если задач приходят тысячи в секунду, эти вставки съедают всё время.
Полный порядок тебе не нужен. Нужно одно: быстро получать наименьшее значение, даже когда новые значения идут потоком. Куча (heap) даёт ровно это. В прошлых уроках ты писал её операции отдельными функциями. Теперь соберёшь их в класс, который можно использовать снова: очередь с приоритетом.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входит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 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- всегда нужен текущий минимум/максимум
- 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
Задачи, где снова и снова выбирают самый срочный элемент, пока прибывают новые, например планировщики задач или учёт свободных мест. Мин-куча отдаёт следующий элемент за O(log n) без повторной сортировки всего.
Счётчик для ещё не взятых чисел плюс мин-куча и множество для чисел, которые вернули.
Отсортируй задачи по времени появления, клади в кучу пришедшие и доставай самую короткую, а при равенстве решает индекс.
Каждый раунд из n + 1 ячеек достаёт из макс-кучи самые частые задачи и возвращает те, у которых остались копии.
Отсортируй проекты по капиталу, клади каждый доступный проект в макс-кучу прибыли и k раз доставай лучший.