c++ - 使用 minheap 实现霍夫曼树

Question

在我在类里面使用的书中(以及我从其他几个地方看到的)，创建霍夫曼树的算法似乎源于

(1) 根据每个字符在任何文件或字符串中被读入的频率构建一个最小堆。

(2) 从最小堆中弹出 2 个最小值并将它们的权重组合到一个新节点中。

(3) 将新节点重新插入到同一个最小堆中。

我对第 3 步感到困惑。我见过的大多数霍夫曼树的属性更类似于最大堆而不是最小堆(尽管它们不是完整的树)。也就是说，根包含最大权重(或者更确切地说是权重组合)，而它的所有子节点都具有较小的权重。当组合的节点被放回最小堆时，这个实现如何给出霍夫曼树？我已经为此苦苦挣扎了一段时间。

类似的问题已经在这里发布(和我同一本书):I don't understand this Huffman algorithm implementation

如果您想查看 (3) 中描述的确切功能。

感谢您的帮助!

Answer 1

霍夫曼树通常不是完全二叉树，因此也不是最小堆。

霍夫曼算法很容易理解为构建树的频率列表。首先构建小分支，最终将全部合并为一棵树。每个列表项都以一个符号开始，后来可能是一个符号或已构建的子树。每个列表项总是有一个频率(通常是整数计数)。

从列表中取出两个最小的频率(平局并不重要——任何选择都会产生一个最优代码，尽管可能有不止一个最优代码)。从这两个构造一个单级二叉树，其中两个叶子是这些频率的符号。添加频率以创建代表树的新频率。将该频率放回列表中。该列表中的频率现在减少了一个。

重复。现在每一步构建的二叉树可能在每个分支上都有符号叶子，或者一个叶子和一个先前构建的树，或者两棵树(最早在第三步)。

继续下去，直到列表中只剩下一个频率。那将是所有原始频率的总和。该频率具有与其关联的完整霍夫曼树。

现在您可以(任意)为每个二进制分支分配一个 0 和一个 1。您可以通过从根遍历树到符号来构建代码或解码代码。来自该遍历分支的位按顺序排列为该符号的霍夫曼代码。