Изменения
→Построение кода Хаффмана
В приведенном ниже псевдокоде предполагается,что <tex>C</tex> - множество,состоящее из <tex>n</tex> символов,и что каждый из символов <tex>c \in C</tex> - объект с определенной частотой <tex>f(c)</tex>.В алгоритме строится оптимальное дерево <tex>T</tex>,соответствующее оптимальному коду,причем построение идет в восходящем направлении.Процесс построения начинается с множества,состоящего из <tex>|C|</tex> листьев,после чего последовательно выполняется <tex>|C|-1</tex> операций "слияния",в результате,которых образуется конечное дерево.Для идентификации двух наименее часто встречающихся объектов,подлежащих слиянию,используется очередь с приоритетами <tex>Q</tex>,ключами в которой являются частоты <tex>f</tex>.В результате слияния двух объектов образуется новый объект,частота появления которого является суммой частот объединенных объектов:
HUFFMAN(<tex>C</tex>)
1 queue <char> <math>\mathrm{Q}</math> 2 <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math> 2 3 <math>\mathrm{Q}</math> = <math>\mathrm{C}</math> 3 4 '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1 4 5 <math>\mathrm{x}</math> = Extract_Min(<math>\mathrm{Q}</math>.extract_min() //Extract_Min extract_min - изъятие из множества наименьшего элемента 5 6 left[<math>\mathrm{z}</math>] = <math>\mathrm{x}</math> 6 7 <math>\mathrm{y}</math> = Extract_Min(<math>\mathrm{Q}</math>.extract_min() 7 8 right[<math>\mathrm{z}</math>] = <math>\mathrm{y}</math> 8 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>] 9 10 Insert(<math>\mathrm{Q}</math>, <math>\mathrm{z}</math>) 10 11 '''return''' Extract_Min(<math>\mathrm{Q}</math>.extract_min() //Возврат корня дерева
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.
