Изменения
→Построение кода Хаффмана
1 queue <char> <math>\mathrm{Q}</math>
2 <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math>
3 <math>\mathrm{Q}</math> =(<math>\mathrm{f}</math>[<math>\mathrm{C}</math>],<math>\mathrm{cC}</math>) //пары в очереди,где f-частота соответствующего символа(ключ),C-множество символов(то есть значение) 4 '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1 0 выделить память для узла Z //чтобы не было претензий по его определению 5 <math>\mathrm{x}</math> = <math>\mathrm{Q}</math>.extract_min() 6 <math>\mathrm{z}</math>.left = <math>\mathrm{x}</math> //z.left-ребенок дерева же 7 <math>\mathrm{y}</math> = <math>\mathrm{Q}</math>.extract_min() 8 <math>\mathrm{z}</math>.right = <math>\mathrm{y}</math> 9 (<math>\mathrm{f}</math>[<math>\mathrm{z}</math>],<math>\mathrm{z}</math>) = (<math>\mathrm{f}</math> [<math>\mathrm{x}</math>] + <math>\mathrm{f}</math>)[<math>\mathrm{y}</math>],(<math>\mathrm{x}</math> + <math>\mathrm{y}</math>) 10 <math>\mathrm{Q}</math>.insert(<math>\mathrm{f}</math>,<math>\mathrm{z}</math>) 11 '''return''' <math>\mathrm{z}</math> //теперь переменная определена
Цикл '''for''' в строках '''4 - 10''' поочередно извлекает по два узла,<tex>x</tex> и <tex>y</tex>,которые характеризуются в очереди с наименьшими частотами,и заменяет их в очереди с новым узлом <tex>z</tex>,представляющим объединение упомянутых выше элементов.Частота появления <tex>z</tex> вычисляется в строке '''9''' как сумма частот <tex>x</tex> и <tex>y</tex>.Узел <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а <tex>y</tex> - его правым дочерним узлом.(Этот порядок является произвольным;перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После <tex>n-1</tex> объединений в очереди остается один узел - корень дерева кодов,который возвращается в строке '''11'''.
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.
