Изменения
→Построение кода Хаффмана
Приведем жадный алгоритм Хаффмана, строящий оптимальный префиксный код. При этом предполагаем, что для любого символа <tex>c \in C</tex> задана его частота <math>\mathrm{f[c]}</math>. Также в алгоритме используется очередь с приоритетами <math>\mathrm{Q}</math>, которая позволяет найти два объекта с наименьшими частотами для их слияния.
n ← |C| Q ← C for i ← 1 to n - 1 do z ← Allocate-Node() x ← left[z] ← Extract-Min(Q) y ← right[z] ← Extract-Min(Q) f[z] ← f[x] + f[y] Insert(Q, z) return Extract-Min(Q)
Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин <math>\mathrm{x}</math> и <math>\mathrm{y}</math> с наменьшими частотами (<math>\mathrm{f[x]}</math> и <math>\mathrm{f[y]}</math> соответственно), которые заменяются на одну вершину <math>\mathrm{z}</math> с частотой <math>\mathrm{f[x]}</math> <math>\mathrm{+}</math> <math>\mathrm{f[y]}</math> и детьми <math>\mathrm{x}</math> и <math>\mathrm{y}</math>.
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.
