Изменения
Нет описания правки
while <math>\mathrm{n}</math> != 1 ''//пока не останется одна частота в массиве''
'''return''' <math>\mathrm{sum}</math>
==Построение кода Хаффмана==
Приведем жадный алгоритм Хаффмена, строящий оптимальный префиксный код — код Хаффмана. При этом предполагаем, что для любого символа <tex>c \in C</tex> задана его частота f[c]. Также в алгоритме используется очередь с приоритетами Q, которая позволяет найти два объекта с наименьшими частотами для их слияния.
Huffman(C)
1 n ← |C|
2 Q ← C
3 for i ← 1 to n - 1
4 do z ← Allocate-Node()
5 x ← left[z] ← Extract-Min(Q)
6 y ← right[z] ← Extract-Min(Q)
7 f[z] ← f[x] + f[y]
8 Insert(Q, z)
9 return Extract-Min(Q)
Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин x и y с наменьшими частотами (f[x] и f[y] соответственно), которые заменяются на одну вершину z с частотой f[x] + f[y] и детьми x и y.
Алгоритм работает за O(nlogn) для алфавита из n символов. Считая что, очередь Q реализована в виде двоичной кучи, мы можем выполнить инициализацию Q за O(n), а каждую операцию над кучей за O(logn).
