Где применяется
1. Задача
Ты хранишь много текста и хочешь, чтобы он занимал меньше места. Простой способ даёт каждой букве одинаковое число битов: 8 бит на e и 8 бит на z. При этом e встречается постоянно, а z почти никогда. Буква, которая встретилась десять тысяч раз, стоит столько же, сколько буква, которая встретилась дважды.
Выгоднее дать частым буквам короткие коды, а редким длинные. Так сжимают файлы gzip, zip и PNG. Остаётся решить, как раздать коды. Общее число битов должно выйти как можно меньше. И читающий должен разобрать поток битов обратно на буквы, хотя между кодами нет разделителей.
Второе условие легко нарушить. Пусть e это 0, а другая буква это 01. Читающий видит 01 и не знает, что перед ним: e и начало следующего кода или та другая буква. Поэтому ни один код не должен совпадать с началом другого кода.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- наименьшее число монет или частей на сумму
- берём самую крупную, что ещё помещается
- выдать сдачу номиналами
- доказать оптимальность обменным аргументом
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
- Бэктрекинг (Backtracking)
Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
- Бинарный поиск по ответу (Binary search on the answer)
Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.
O(n log n), если вход сначала нужно отсортировать. Проход после сортировки это один цикл, O(n).
На LeetCode
На LeetCode нет бесплатной задачи на построение кодов Хаффмана. Две самые близкие, Minimum Cost to Connect Sticks (1167) и Minimum Time to Build Blocks (1199), платные. Шаг с кучей, который повторяет Хаффман, соединение двух самых маленьких, есть в бесплатных задачах урока 109.