Где применяется
1. Задача
До сих пор жадные алгоритмы выбирали в заранее известном порядке. Планирование интервалов один раз сортировало заявки по времени конца и потом шло по списку; аргумент обмена доказывал, что одной сортировки достаточно. Здесь порядок всё время меняется. Ты объединяешь элементы, и каждое объединение создаёт новый элемент, который надо сравнивать со всеми оставшимися. Две самые маленькие величины, нужные на следующем шаге, меняются после каждого хода, поэтому одна сортировка в начале их не даст.
Конкретная задача. Есть несколько файлов размером [1, 2, 3, 4], их надо слить в один. За раз можно слить только два файла, и слияние стоит столько работы, сколько весят оба файла вместе. Слитый файл возвращается в общий набор и может слиться ещё раз. Нужна наименьшая общая стоимость всех слияний, после которых останется один файл.
От порядка слияний зависит итог. Слить 1+2=3 (стоимость 3), потом 3+3=6 (стоимость 6), потом 4+6=10 (стоимость 10): итог 19. Если каждый раз брать два самых больших файла, выйдет 4+3=7, 7+2=9, 9+1=10, итог 7 + 9 + 10 = 26. Маленькие файлы тогда раз за разом входят в крупные слияния, и итог растёт.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где снова и снова берут два самых маленьких или два самых больших значения, объединяют их и кладут результат обратно. Куча отдаёт оба значения за O(log n) на каждом шаге. Ровно задача урока на LeetCode это Minimum Cost to Connect Sticks (1167), но она платная.
Достань два самых маленьких, положи меньшее, умноженное на 2, плюс большее и считай шаги, пока наименьшее не дойдёт до k. Это цикл урока с другой формулой слияния.
Тот же цикл с макс-кучей. Разбей два самых тяжёлых камня и положи обратно разницу, если она больше нуля.
Каждую секунду наполняй по одной чашке двух типов, где их осталось больше всего, то есть доставай два наибольших счёта, уменьшай каждый на один и клади обратно.