Где применяется
1. Задача
На шаге 80 куча росла по одному элементу: ты добавлял значение в конец, и оно поднималось вверх (просеивание вверх). Теперь у тебя сразу целый массив чисел. Его нужно превратить в кучу за один проход, а потом раз за разом доставать из неё самое маленькое значение.
Можно добавлять числа в новую кучу по одному. Это работает, но стоит O(n log n): n вставок, и каждое значение может подняться на высоту до log n уровней. Есть способ быстрее. Он переставляет числа прямо в том массиве, который у тебя уже есть, и тратит O(n).
Когда куча готова, нужна вторая операция: забрать самое маленькое значение и оставить правильную кучу, которая готова отдать следующее. Обе задачи решает один новый ход, обратный просеиванию вверх: просеивание вниз (sift down).
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи-симуляции, где много раз берут наибольший или наименьший элемент и кладут обратно изменённый. Построй кучу из входа за O(n), а дальше каждое извлечение и вставка стоят O(log n).
Построй макс-кучу, достань два самых тяжёлых и положи обратно разницу, если она не ноль.
Построй из кучек макс-кучу, потом k раз доставай наибольшую и клади обратно её квадратный корень с округлением вниз.
Тот же цикл, каждый раз убираешь половину самой большой кучки, а n и k доходят до 10^5, так что пересортировка на каждом шаге слишком медленная.