我不明白这个霍夫曼算法的实现 [英] I don't understand this Huffman algorithm implementation

问题描述

    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编码的2页定义以及上面的代码。对我来说，这本书的细节不够详细，所以我做了谷歌搜索，我了解了霍夫曼编码的过程如何工作。教科书声称，在上述代码的最后，制作了一个霍夫曼树。但是对我来说似乎是错误的，因为霍夫曼树并不需要一棵完整的树，但上面的代码似乎总是给出一个完整的树，因为 heap.push（）。那么有人可以向我解释一下这段代码是不是错了？

In my Fundamentals of Data Structures in C++ textbook, it gave a 2 page definition of Huffman coding, and the code above. To me, the book wasn't enough detailed, so I've done the googling and I learned how the process of Huffman coding works. The textbook claims that at the end of the code above, a Huffman tree is made. But to me it seems wrong, because a Huffman tree, is not necessary a complete tree, but the code above seems to always give a complete tree because of the heap.push(). So can someone explain to me how this piece of code is not wrong?

推荐答案

堆的树结构不一定与得到的霍夫曼树相符，而是堆包含部分霍夫曼树，最初每个由单个符号节点组成。循环然后重复地以最小权重取得两个节点，将它们组合成一个节点，并将结果组合节点放回。在进程结束时，堆中包含一个已完成的树。

The heap's tree structure does not necessarily match the resulting Huffman tree -- rather, the heap contains a forest of partial Huffman trees, initially each consisting of a single symbol node. The loop then repeatedly takes the two nodes with the least weight, combines them into one node, and puts the resulting combined node back. At the end of the process, the heap contains one finished tree.

这篇关于我不明白这个霍夫曼算法的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！