Изменения

Приведем жадный алгоритм ХаффменаХаффмана, строящий оптимальный префиксный код — код Хаффмана. При этом предполагаем, что для любого символа <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>.

Алгоритм работает за O(nlogn) для алфавита из <math>\mathrm{n }</math> символов. Считая что, очередь Q реализована в виде двоичной кучи, мы можем выполнить инициализацию Q за O(n), а каждую операцию над кучей за O(logn).