Где применяется
1. Задача
В прошлых уроках одна куча отдавала самое маленькое значение. Здесь куч будет две, и вопрос другой: какое значение сейчас стоит в середине всех пришедших данных. Ответ должен обновляться после каждого нового числа.
Числа приходят потоком, например замеры задержки. После каждого числа нужна текущая медиана. Медиана это значение, которое стоит посередине, если всё пришедшее отсортировать. Она хорошо показывает типичное значение: один огромный всплеск сильно сдвигает среднее арифметическое и почти не меняет медиану. Например, у замеров 10, 11, 12 и 1000 среднее больше 250, а медиана 11,5.
Можно держать отсортированный массив и читать его середину. Читать легко, но каждое новое число приходится вставлять на место, сдвигая элементы. Одна вставка стоит O(n), и на длинном потоке это слишком медленно. Нужна середина без поддержания полного порядка.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 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
Задачи, где нужна медиана или другое среднее значение, пока числа продолжают прибывать. Макс-куча держит нижнюю половину, мин-куча верхнюю, а их корни дают середину.
runningMedian из урока в виде класса с addNum и findMedian.
Те же две кучи плюс ленивое удаление, значение, ушедшее из окна, помечается в словаре и выбрасывается, когда доходит до корня.
Две кучи делятся на i-м лучшем месте, и каждый вызов get сдвигает эту границу на одно место.