Где применяется
1. Задача
В прошлых уроках ты построил кучу, и она дёшево отдаёт самый маленький элемент. Теперь первая настоящая задача для неё. У тебя несколько списков, и каждый уже отсортирован. Например, логи с k серверов, каждый по времени. Нужен один общий поток, тоже по времени.
Можно склеить всё в один массив и отсортировать заново. Но тогда готовый порядок внутри списков пропадает зря, а все строки приходится держать в памяти одновременно. Для нескольких огромных потоков это дорого. К тому же первую строку результата нельзя выдать, пока не загружены все.
Лучше идти по общему порядку по одному элементу: каждый раз выдавать наименьшее ещё не выданное значение и смотреть при этом на как можно меньшее число элементов.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 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 отсортированным последовательностям одновременно. Держи в мин-куче первый элемент каждого списка, доставай наименьший и клади следующий из того же списка.
mergeK из урока на связных списках, в куче лежат узлы, а не позиции.
Каждая строка это отсортированный список, так что положи в кучу первый элемент каждой строки и извлеки k раз.
Считай пары для каждого nums1[i] одним отсортированным списком, и то же слияние даёт первые k пар.
Держи в куче по одному элементу из каждого списка и следи за текущим максимумом, тогда диапазон равен этому максимуму минус корень кучи.