在我上课使用的书中(以及从其他地方看到的内容)，创建霍夫曼树的算法似乎源于
(1)根据要读取的文件或字符串中每个字符的频率构建最小堆。
(2)从最小堆中弹出两个最小值，并将它们的权重合并到一个新节点中。
(3)将新节点重新插入到同一minheap中。
我对第3步感到困惑。我见过的大多数霍夫曼树的属性与最小堆相比更类似于最大堆(尽管它们不是完整的树)。也就是说，根包含最大权重(或权重的组合)，而所有子代的权重都较小。当将合并的节点放回minheap中时，此实现如何产生霍夫曼树？我已经为此苦了一段时间了。
一个类似的问题已经发布在这里(与我同本):I don't understand this Huffman algorithm implementation
如果您想查看(3)中描述的确切功能。
谢谢你的帮助!
最佳答案
霍夫曼树通常不是完整的二叉树，因此也不是最小堆。
霍夫曼算法很容易理解为构建树的频率列表。首先构造小分支，最终将所有小分支合并为一棵树。每个列表项均以符号开头，以后可以是符号或已构建的子树。每个列表项始终有一个频率(通常是整数)。
从列表中减去两个最小的频率(关系并不重要-任何选择都会产生最佳代码，尽管可能有多个最佳代码)。从那两个构建一个单级二叉树，其中两个叶子是这些频率的符号。添加频率以创建代表树的新频率。将该频率放回列表中。现在，列表中的频率减少了一个。
重复。现在，在每个步骤中构造的二叉树可能在每个分支上具有符号叶，或者在一个叶子上有一个先前构造的树，或者在第二个步骤中最早有两棵树。
继续前进直到列表中只剩下一个频率。那将是所有原始频率的总和。该频率具有与之关联的完整霍夫曼树。
现在，您可以(任意)为每个二进制分支分配0和1。您可以通过从根到符号遍历树来构建代码或解码代码。该遍历分支中的位按该符号的霍夫曼编码排序。