Изменения

€€В приведенном ниже псевдокоде предполагается,что <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>C</tex>) struct Node //Звено дерева int <math>\mathrm{key}</math>, char <math>\mathrm{value}</math> //пара ключ и значение Node *left,*right <math>\mathrm{n}</math> = |<math>\mathrm{|C|}</math>| queue <char> <math>\mathrm{Q}</math> = char <math>\mathrm{c}</math>[<math>\mathrm{n}</math>] , int <math>\mathrm{f}</math>[<math>\mathrm{Cn}</math>] //массив c содержит алфавит из n различных символов,массив f - соответствующий ему набор положительных целых весов. '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - <math>\mathrm{Q}</math>.insert(<math>\mathrm{f}</math>[<math>\mathrm{i}</math>],<math>\mathrm{c}</math>[<math>\mathrm{i}</math>]) '''for''' <math>\mathrm{i}</math> = 1 '''doto''' Выделить память для узла <math>\mathrm{zn}</math> - 1 (<math>\mathrm{min1}</math>,<math>\mathrm{x}</math> ) = Extract_Min(<math>\mathrm{Q}</math>.extract_min() //Extract_Min - изъятие из множества наименьшего элемента left[ <math>\mathrm{z}</math>] .left = <math>\mathrm{x}</math> (<math>\mathrm{min2}</math>,<math>\mathrm{y}</math> ) = Extract_Min(<math>\mathrm{Q}</math>.extract_min() right[ <math>\mathrm{z}</math>] .right = <math>\mathrm{y}</math> <math>\mathrm{f[z]sum}</math> = <math>\mathrm{f[x]min1}</math> + <math>\mathrm{f[y]min2}</math> INSERT <math>\mathrm{Q}</math>.insert(<math>\mathrm{Qsum}</math>, <math>\mathrm{z}</math>) '''return''' Extract_Min(<math>\mathrm{Qz}</math>) //Возврат корня дерева