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

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++数据结构基础 教科书中,它给出了霍夫曼编码的2页定义,以及上面的代码.对我来说,这本书不够详细,所以我已经完成了谷歌搜索,我学会了霍夫曼编码的过程.教科书声称在上面的代码末尾,制作了霍夫曼树.但对我来说这似乎是错误的,因为霍夫曼树不是一个完整的树,但上面的代码似乎总是给出一个完整的树,因为heap.push().那么有人可以向我解释这段代码是如何没有错的吗？

Answer 1

堆的树结构不一定与得到的霍夫曼树匹配 - 相反,堆包含部分霍夫曼树的森林,最初每个树由单个符号节点组成.然后,循环重复获取具有最小权重的两个节点,将它们组合成一个节点,并将得到的组合节点放回.在进程结束时,堆包含一个完成的树.