Изменения

Приведем жадный алгоритм Хаффмена€В приведенном ниже псевдокоде предполагается, строящий оптимальный префиксный код — код Хаффмана. При этом предполагаемчто <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{n}</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 '''to''' <math>\mathrm{n}</math> - 1 (<math>\mathrm{min1}</math>,<math>\mathrm{x}</math>) = <math>\mathrm{Q}</math>.extract_min() <math>\mathrm{z}</math>.left = <math>\mathrm{x}</math> (<math>\mathrm{min2}</math>,<math>\mathrm{y}</math>) = <math>\mathrm{Q}</math>.extract_min() <math>\mathrm{z}</math>.right = <math>\mathrm{y}</math> <math>\mathrm{sum}</math> = <math>\mathrm{min1}</math> + <math>\mathrm{min2}</math> <math>\mathrm{Q}</math>.insert(<math>\mathrm{sum}</math>,<math>\mathrm{z}</math>) '''return''' <math>\mathrm{z}</math>

Алгоритм работает за <tex> {O(nlognn\log{n}}) </tex> для алфавита из <math>\mathrm{n }</math> символов. Считая что, очередь Q реализована в виде двоичной кучи, мы можем выполнить инициализацию Q за O(n), а каждую операцию над кучей за O(logn).