Я не понимаю эту реализацию алгоритма Хаффмана

Question

    template<class T>
    void huffman(MinHeap<TreeNode<T>*> heap, int n)
    {
      for(int i=0;i<n-1;i++)
      {
        TreeNode<T> *first = heap.pop();
        TreeNode<T> *second = heap.pop();
        TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data, second.data);
        heap.push(bt);
      }
    }

В моем Основах структур данных в C ++ учебнике он дал двухстраничное определение кодирования Хаффмана и приведенный выше код. Для меня книга была недостаточно детальной, поэтому я занялся поиском и узнал, как работает процесс кодирования Хаффмана. В учебнике утверждается, что в конце кода выше получено дерево Хаффмана. Но мне кажется, что это неправильно, поскольку дерево Хаффмана не является необходимым полным деревом, но приведенный выше код, похоже, всегда дает полное дерево из-за heap.push(). Так может кто-нибудь объяснить мне, как этот кусок кода не так?

Answer 1

Структура дерева кучи не обязательно совпадает с результирующим деревом Хаффмана - скорее, куча содержит лес частичных деревьев Хаффмана, изначально каждое из которых состоит из одного узла символа. Затем цикл повторно принимает два узла с наименьшим весом, объединяет их в один узел и возвращает полученный объединенный узел обратно. В конце процесса куча содержит одно законченное дерево.

Answer 2

Кодирование Хаффмана работает, принимая два элемента с наименьшим значением на каждом шаге.Когда вы впервые вызываете функцию (поскольку ваш MinHeap отсортирован по значению), два элемента с наименьшим значением выталкиваются и «объединяются» в узел принятия решения, который затем помещается обратно в кучу.Этот узел оценивается суммой его дочерних оценок и помещается обратно в кучу.Вставка его обратно в кучу помещает его в нужное место на основе его оценки;если он все еще ниже, чем любые другие элементы, он будет первым, в противном случае он будет где-то еще.

Так что этот алгоритм строит дерево снизу вверх, и к тому времени, когда вы очищаете кучу, вы 'будет полное деревоЯ не понимаю, для чего 'n', хотя;цикл должен быть while (heap.size() > 1).Несмотря на это, дерево не является «полным», разные ветви будут иметь разную длину в зависимости от того, как оцениваются частоты элементов в начальной куче.