1632
правки
Изменения
м
1 <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math>
2 <math>\mathrm{Q}</math> = <math>\mathrm{C}</math>
3 '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1
4 '''do''' Выделить память для узла <math>\mathrm{z}</math>
5 <math>\mathrm{x}</math> = Extract_Min(<math>\mathrm{Q}</math>) //Extract_Min - изъятие из множества наименьшего элемента
6 left[<math>\mathrm{z}</math>] = <math>\mathrm{x}</math>
7 <math>\mathrm{y}</math> = Extract_Min(<math>\mathrm{Q}</math>)
8 right[<math>\mathrm{z}</math>] = <math>\mathrm{y}</math>
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''' Extract_Min(<math>\mathrm{Q}</math>) //Возврат корня дерева
В строке <tex>2</tex> инициализируется очередь с приоритетом <tex>Q</tex>,состоящая из элементов множества <tex>C</tex>.Цикл '''for''' в строках '''3 - 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'''.
rollbackEdits.php mass rollback
==Построение кода Хаффмана==
В приведенном ниже псевдокоде предполагается,что <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|}<tex/math> queue <char> <math>\mathrm{Q}</math> char <math>\mathrm{c}</math>[<math>\mathrm{n}</math>] , int <math>\mathrm{f}</texmath>[<math>\mathrm{n}</math>] //массив c содержит алфавит из n различных символов,ключами в которой являются частоты массив f - соответствующий ему набор положительных целых весов. '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> <math>\mathrm{Q}</math>.insert(<texmath>\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}</texmath> <math>\mathrm{Q}</math>.В результате слияния двух объектов образуется новый объектinsert(<math>\mathrm{sum}</math>,частота появления которого является суммой частот объединенных объектов:<math>\mathrm{z}</math>) '''return''' <math>\mathrm{z}</math>
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.
