Изменения

Перейти к: навигация, поиск
Построение кода Хаффмана
3 <math>\mathrm{Q}</math> = <math>\mathrm{C}</math>
4 '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1
5 <math>\mathrm{x}</math> = <math>\mathrm{Q}</math>.extract_min() //extract_min - изъятие из множества наименьшего элемента
6 <math>\mathrm{z}</math>.left = <math>\mathrm{x}</math>
7 <math>\mathrm{y}</math> = <math>\mathrm{Q}</math>.extract_min()
9 <math>\mathrm{f}</math>[<math>\mathrm{z}</math>] = <math>\mathrm{f}</math>[<math>\mathrm{x}</math>] + <math>\mathrm{f}</math>[<math>\mathrm{y}</math>]
10 Insert(<math>\mathrm{Q}</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> символов.
Анонимный участник

Навигация