Изменения

На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами, содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По скольку данное множество содержит шесть букв, размер исходной очереди равен 6(часть ''а '' рисунка), а для построения дерева требуется пять слияний. Промежуточные этапы изображены в частях ''б-д''. Конечное дерево (''е'') представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой. <br> В строке 2 инициализируется очередь с приоритетами <tex>Q</tex>, состоящая из элементов множества <tex>С</tex>. Цикл '''for ''' в строках 3-8 поочередно извлекает по два узла, х <tex>x</tex> и <tex>у</tex>, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом z, представляющим объединение упомянутых выше элементов. Частота появления <tex>z </tex> вычисляется в строке 7 как сумма частот х <tex>x</tex> и у<tex>y</tex>. Узел х <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а у <tex>y</tex> — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После п — <tex>n - 1 </tex> объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9. === Оценка времени работы ===При анализе времени работы алгоритма Хаффмана предполагается, что <tex>Q </tex> реализована как бинарная неубывающая пирамида (см. главу 6). Для множества С<tex>C</tex>, состоящего из п <tex>n</tex> символов, инициализацию очереди <tex>Q </tex> в строке 2 можно выполнить 464 Часть IV. Усовершенствованные методы разработки и анализа за время О <tex>O(пn) с помощью процедуры Build_Min_Heap из раздела 6.3</tex>. Цикл for в строках 3-8 выполняется ровно и — <tex>n - 1 </tex> раз, и поскольку для каждой операции над пирамидой требуется время О <tex>O(lg(lgnn))</tex>, вклад цикла во время работы алгоритма равен <tex>O(nlgnn \cdot lg(n))</tex>. Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из п <tex>n</tex> символов, равно О <tex>O(n \cdot lg(nlgnn))</tex>.