Хаффман реализации дерева с использованием minheap

Question

В книге я использую для моего класса (и от того, что я видел от нескольких других мест), кажется, что алгоритм создавая дерево Хаффмана происходит от

(1) Построение minheap, основанного на частоте каждого символа в любом файле или строке, считывается.

(2) Отбрасывание двух наименьших значений из minheap и объединение их весов в новый узел.

(3) Повторная установка нового узла обратно в тот же самый миниатюрный.

Я смущен о шаге 3. Большинство деревьев хаффмана, которые я видел, имеют атрибуты, более похожие на максимальную кучу, чем минеап (хотя они не являются полными деревьями). То есть корень содержит максимальный вес (или комбинацию весов), в то время как все его дети имеют меньшие веса. Как эта реализация дает дерево хаффмана, когда объединенные узлы возвращаются в миниатюру? Некоторое время я боролся с этим.

Аналогичный вопрос уже размещен здесь (с той же книге, как мне): I don't understand this Huffman algorithm implementation

В случае, если вы хотите, чтобы увидеть точную функцию, описанную в (3).

Спасибо за помощь!

Answer 1

Дерево Хаффмана часто не полное двоичное дерево, и, следовательно, не является мини-кучей.

Алгоритм Хаффмана легко понять как список частот, из которых построено дерево. Сначала создаются небольшие ветви, которые в конечном итоге будут объединены в единое дерево. Каждый элемент списка начинается как символ, а позже может быть символом или поддеревом, которое было создано. Каждый элемент списка всегда имеет частоту (обычно число целых чисел).

Возьмите две наименьшие частоты из списка (связи не имеют значения - любой выбор приведет к созданию оптимального кода, хотя может быть более одного оптимального кода). Создайте одноуровневое двоичное дерево из этих двух, где два листа являются символами для этих частот. Добавьте частоты, чтобы создать новую частоту, представляющую дерево. Верните эту частоту в список. Список теперь имеет в нем одну меньшую частоту.

Повторите. Теперь бинарное дерево, построенное на каждом шаге, может иметь символ на каждой ветви, или один лист, и ранее построенное дерево, или два дерева (как можно раньше на третьем шаге).

Продолжайте движение, пока в списке не останется только одна частота. Это будет сумма всех исходных частот. Эта частота имеет полное дерево Хаффмана, связанное с ней.

Теперь вы можете (произвольно) назначить 0 и 1 на каждую двоичную ветвь. Вы создаете коды или декодируете коды, перемещая дерево от корня к символу. Биты из ветвей этого траверса соответствуют порядку Хаффмана для этого символа.