Изменения

Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые "символы" с частотой равной сумме частот тех символов, которые мы объединяли.

В примере мы объединим символы b и с в символ bc с частотой 3.

Хаффман изобрел жадный алгоритм, позволяющий составить оптимальный префиксный код, который получил название код Хаффмана. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора и оптимальной подструктуре. Вместо того чтобы демонстрировать, что эти свойства выполняются, а затем разрабатывать псевдокод, сначала мы представим псевдокод. Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что <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> операций "слияния", в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами <tex>Q</tex>, ключами в которой являются частоты <tex>f</tex>. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов: