我不理解这个Huffman算法的实现。

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++数据结构基础教材《数据结构基础》中，对于Huffman编码及其上方的代码只给了两页定义。但对我而言，这些内容都不够详细，所以我进行了搜索，学习了Huffman编码的过程。教材声称该代码可以生成一棵Huffman树，但在我看来这是错误的。因为Huffman树不一定是完全二叉树，但由于heap.push()语句的存在，上述代码似乎总是生成一个完全二叉树。有没有人能够解释一下这段代码为何不会出错呢？

- user299648

Answer 1

堆的树形结构不一定与最终的霍夫曼树相匹配——相反，堆包含一些部分霍夫曼树的森林，最初每个森林都只包含一个符号节点。然后循环地取出权重最小的两个节点，将它们合并为一个节点，并将结果合并后的节点放回堆中。在过程结束时，堆只包含一棵完整的霍夫曼树。

- Jeffrey Hantin

---

那么我不明白的是，如果堆不一定是哈夫曼树，那么我如何遍历或使用堆来找到正确的叶节点。 - user299648

堆是一种临时辅助数据结构，用于提高查找最小权重的两个Huffman节点的操作效率。最终，堆仅包含一个元素，即单个BinaryTreeNode<T>，可以弹出并成为完成的Huffman树的根；然后可以销毁堆，因为它不再需要。 - Jeffrey Hantin

Answer 2

Huffman编码的工作方式是在每一步中取两个最小值。当您第一次调用函数时（因为MinHeap按值排序），将弹出两个最小值并将它们“组合”成一个决策节点，然后将其放回到堆中。该节点的得分是其子节点得分之和，并将其放回堆中。将其重新插入堆中会根据其得分将其放置在正确的位置；如果它仍然低于任何其他项，它将排在首位，否则它将在其他地方。

因此，这个算法是从底部向上构建树形结构的，当您清空堆时，您将拥有一棵完整的树。我不明白'n'是用来干什么的，但循环应该是while (heap.size() > 1)。无论如何，树都不是“完整的”，不同的分支长度将取决于初始堆中项目的频率得分。

- dash-tom-bang