Изменения

# <tex>n \gets |C|</tex> <br># <tex>Q \gets C</tex> <br># '''for''' <tex>i \gets 1</tex> '''to''' <tex>n - 1</tex> <br>:# '''do''' Выделить память для узла <tex>z</tex> <br># ::left[<tex> z</tex>] «- х <- tex> \gets x \gets</tex> Extract_Min(<tex> Q</tex>)<br> # ::right[<tex>z</tex>] <- у tex>\gets y \gets <- ExtractJMin/tex> Extract_Min(<tex>Q</tex>) <br># ::<tex>f[z] \gets f[x]+f[y]</tex> ::Insert(<tex>Q</tex>, <tex>z</tex> ) <br># '''return ''' Extract_Min(<tex>Q</tex> ) <tex> \rhd </tex> Возврат корня дерева <br><br>Для рассмотренного ранее примера алгоритм Хаффмана выводит результат, при- === Пример работы алгоритма ===веденный на рис. 16.4[[Файл:Huffman. jpg]]<br>На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге рабо- ты работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами* содер- жащими , содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым до- черним дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По- Глава 16. Жадные алгоритмы 463 a) if-л] [^) I \у:\2\ <> П| |d IM |.,.4S| 6) Ki2) ЬИ в) ® ШЕ ® ШШ о/ \i о/ 1Ж11Ж1 о/ \> t 5 р ч л) ЕВЕ (inn) о ч \ I f7i2i |b 13 f) i Рис. 16.4. Этапы работы алгоритма Хаффмана для частот, заданных в табл. 16.1 сколысу скольку данное множество содержит шесть букв, размер исходной очереди равен 6 (часть а рисунка), а для построения дерева требуется пять слияний. Промежуточ- ные Промежуточные этапы изображены в частях б-д. Конечное дерево (рис. 16.4ее) представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой. В строке 2 инициализируется очередь с приоритетами Q, состоящая из эле- ментов элементов множества С. Цикл for в строках 3-8 поочередно извлекает по два узла, х и у, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом z, представляющим объединение упомянутых выше элементов. Частота появления z вычисляется в строке 7 как сумма частот х и у. Узел х является левым дочерним узлом z, а у — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После п — 1 объедине- ний объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9. При анализе времени работы алгоритма Хаффмана предполагается, что Q реа- лизована реализована как бинарная неубывающая пирамида (см. главу 6). Для множества С, со- стоящего состоящего из п символов, инициализацию очереди Q в строке 2 можно выполнить 464 Часть IV. Усовершенствованные методы разработки и анализа за время О (п) с помощью процедуры Build_Min_Heap из раздела 6.3. Цикл for в строках 3-8 выполняется ровно и — 1 раз, и поскольку для каждой операции над пирамидой требуется время О (lgn), вклад цикла во время работы алгорит- ма алгоритма равен O(nlgn). Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из п символов, равно О (nlgn).  == Корректность алгоритма Хаффмана ==

сес сес = f [x] dT (х) + f [a] dT (а) - f [x] dT, (х) - / [a] dT> (а) = = / [х] dT (х) + / [a] dT (а) - / [х] dT (а) - / [а] dT (x) = = (f[a]-f[x})(dT(a)-dT(x))>0,

{{Теорема 16.4. |id=th1|statement=Процедура Huffman дает оптимальный префиксный код. Доказательство. |proof=Справедливость теоремы непосредственно следует из лемм 16.1 и 2 и 16.3.}}