c++ - 我不明白这个霍夫曼算法的实现

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);
      }
    }

在我的Fundamentals of Data Structures in C++教科书，它给出了霍夫曼编码的 2 页定义，以及上面的代码。对我来说，这本书不够详细，所以我进行了谷歌搜索，了解了霍夫曼编码的过程是如何工作的。教科书声称在上面代码的最后，制作了一个霍夫曼树。但对我来说这似乎是错误的，因为霍夫曼树不一定是完整的树，但由于 heap.push()，上面的代码似乎总是给出完整的树。那么有人能给我解释一下这段代码怎么没有错吗？

Answer 1

堆的树结构不一定与生成的霍夫曼树匹配——相反，堆包含部分霍夫曼树的森林，每棵树最初都由一个符号节点组成。然后循环重复取权重最小的两个节点，将它们合并为一个节点，并将合并后的节点放回去。在该过程结束时，堆中包含一棵完成的树。