Каков наиболее эффективный (*) способ построения канонического дерева Хаффмана?

Question

Предположим, что A - это массив, где A [0] содержит частоту 0-й буквы алфавита.

Какой самый эффективный (*) способ вычисления длины кода? Не уверен, но, думаю, эффективность может быть связана с использованием памяти или необходимыми шагами.

Все, что меня интересует, это массив L, где L[0] содержит длины кода (количество битов) от 0-й буквы алфавита, где код взят из канонического дерева Хаффмана, построенного из частотного массива.

Answer 1

Если частоты образуют монотонную последовательность, т.е.A [0] <= A [1] <= ... <= A [n-1] или A [0]> = A [1]> = ...> = A [n-1], тогда выможет генерировать оптимальные длины кода за O (n) времени и O (1) дополнительного пространства.Этот алгоритм требует всего 2 простых прохода по массиву, и он очень быстрый.Полное описание приведено в [1].

Если ваши частоты не отсортированы, сначала вам нужно отсортировать их, а затем применить вышеописанный алгоритм.В этом случае временная сложность равна O (n log n), и для хранения отсортированного порядка необходим вспомогательный массив из n целых чисел - сложность пространства O (n).

[1]: вычисление минимумаКоды резервирования Алистера Моффата и Юрки Катаяйнена, доступные онлайн: http://www.diku.dk/~jyrki/Paper/WADS95.pdf