Изменения

Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго. Достаточно лишь находить л.м.с.п., при этом не важно, в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <tex>n</tex>, из которого мы будем удалять л.м.с.п и создавать новую вершину. На нем легко будет осуществлять поиск л.м.с.п. А так же необходим массив размера <tex>2n</tex> для реализации следующего шага, хранящий дерево. Второй шаг легко осуществить проходом по дереву, имея сохраненное дерево. Третий шаг, реализованный стековым алгоритмом, работает за <tex>2n</tex> времени и требует <tex>4n</tex> памяти <tex>n</tex> на стек, <tex>n</tex> на хранения уровней вершин и <tex>2n</tex> на хранение итогового дерева. Итак, общая оценка как раз получается <tex>O(n)</tex> памяти и <tex>O(n \log n)</tex> времени.

* [[Алгоритм Хаффмана]]

* [[Избыточное кодирование, код Хэмминга]]