Изменения

€В приведенном ниже псевдокоде предполагается,что <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> операций "слияния",в результате,которых образуется конечное дерево.Для идентификации двух наименее часто встречающихся объектов,подлежащих слиянию,используется очередь с приоритетами HUFFMAN(<tex>QC</tex>) struct Node //Звено дерева int <math>\mathrm{key}</math>,ключами в которой являются частоты char <texmath>f\mathrm{value}</texmath>.В результате слияния двух объектов образуется новый объект //пара ключ и значение Node *left,частота появления которого является суммой частот объединенных объектов:*right HUFFMAN( <math>\mathrm{n}</math> = <texmath>\mathrm{|C|}</texmath>) 1 queue <char> <math>\mathrm{Q}</math> 2 char <math>\mathrm{nc}</math> = [<math>\mathrm{|C|n}</math> 3 ] , int <math>\mathrm{Qf}</math> = [<math>\mathrm{Cn}</math>] //массив c содержит алфавит из n различных символов,массив f - соответствующий ему набор положительных целых весов. 4 '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1 5 <math>\mathrm{Q}</math>.insert(<math>\mathrm{xf}</math> = [<math>\mathrm{Qi}</math>.extract_min( ],<math>\mathrm{c}</math>[<math>\mathrm{i}</extract_min - изъятие из множества наименьшего элементаmath>]) 6 '''for''' <math>\mathrm{zi}</math>.left = 1 '''to''' <math>\mathrm{xn}</math>- 1 7 (<math>\mathrm{min1}</math>,<math>\mathrm{yx}</math> ) = <math>\mathrm{Q}</math>.extract_min() 8 <math>\mathrm{z}</math>.right left = <math>\mathrm{x}</math> (<math>\mathrm{min2}</math>,<math>\mathrm{y}</math> 9 ) = <math>\mathrm{fQ}</math>[.extract_min() <math>\mathrm{z}</math>] .right = <math>\mathrm{fy}</math> <math>\mathrm{sum}</math>[= <math>\mathrm{xmin1}</math>] + <math>\mathrm{fmin2}</math>[ <math>\mathrm{yQ}</math>] 10 Insert.insert(<math>\mathrm{Qsum}</math>, <math>\mathrm{z}</math>) 11 '''return''' <math>\mathrm{z}</math> //Возврат корня дерева