Изменения

Приведем жадный алгоритм Хаффмана, строящий оптимальный префиксный код. При этом предполагаем, что для любого символа <tex>c \in C</tex> задана его частота <math>\mathrm{f[c]}</math>. Также в алгоритме используется очередь с приоритетами <math>\mathrm{Q}</math>, которая позволяет найти два объекта с наименьшими частотами для их слияния.

Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин <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> символов.