==Построение кода Хаффмана==
Приведем жадный алгоритм Хаффмана, строящий оптимальный префиксный код. При этом предполагаем, что <math>\mathrm{n}</math> = |<math>\mathrm{C}</math>| <math>\mathrm{Q}</math> = <math>\mathrm{C}</math> for <math>\mathrm{i}</math> = 1 to <math>\mathrm{n}</math> - 1 do Выделить память для любого символа узла <math>\mathrm{z}</math> <math>\mathrm{x}</math> = Extract_Min(<math>\mathrm{Q}</math>) left[<texmath>c \in Cmathrm{z}</math>] = <math>\mathrm{x}</math> <math>\mathrm{y}</math> = Extract_Min(<math>\mathrm{Q}</math>) right[<math>\mathrm{z}</math>] = <math>\mathrm{y}</math> <math>\mathrm{f[z]}</math> = <math>\mathrm{f[x]}</texmath> задана его частота + <math>\mathrm{f[cy]}</math>. Также в алгоритме используется очередь с приоритетами INSERT(<math>\mathrm{Q}</math>, которая позволяет найти два объекта с наименьшими частотами для их слияния.<math>\mathrm{z}</math>) return Extract_Min(<math>\mathrm{Q}</math>) //Возврат корня дерева
<math>\mathrm{n}</math> ← |C|
<math>\mathrm{Q}</math> ← 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> символов.
