哈夫曼树及其编码

BYR_KKK · 2023-12-01 13:01:50 · 个人记录

前置知识——WPL

在一棵二叉树上，我们把根节点到 x 的最短路径长度（显然为 x 的深度） 乘上其权值 w_x 得到的结果称为 x 的带权路径长度。

所有叶子节点的带权路径长度之和即为 WPL 。

形式化地，设所有叶子节点为 a_1,a_2,a_3,\ldots,a_n ，深度为 h_1,h_2,h_3\ldots,h_n（这里规定根节点的深度为 0），权值为 w_1,w_2,w_3,\ldots,w_n ，则有：

在知晓每点权值的基础上，哈夫曼树的 WPL 最小。（每个权值都要放在叶子上）

因此其又被称为“最优树”。

构造

贪心地想，当权值越大的点的深度（h_i）越小时，这棵树的 WPL 越小。

利用合并果子的思想，一开始将每个点看做单独的一棵树，随后每次选择权值最小的两棵树合并，权值相加，变成一颗新树，直到只剩一棵树。

可以证明，哈夫曼树的 WPL 值最小。

关于 WPL 值的求法。

每次将合并出来的新树的权值和加入到答案中即可。这里感性理解，每次合并后新树种每个节点的到根的路径长度都会加一，利用乘法分配律来理解。

k叉哈夫曼树

类比二叉树。

每次从堆中取出前 k 小的树合并，但是当最后一次合并时堆中的树小于 k 时，此时一定不是最优。

例如当 k=3 时，我们需要对 4 个点进行合并：

我们如果把合并后的树中随意一个底层的点拿上来都可以更优。

请结合这段话与画图进行理解：

所以我们只需加上一些权值为 0 的点，这样这些点会“挤占”有权值的点的位置（因为它们的权值最小，最先被选中），并且权值为 0 ，不会对答案产生减小的影响。

最终要使节点总数 n 满足 n\%(k-1)=1 （每次合并会减少 k-1 个点，最终要剩下一棵最终的树）。

这里建议写成 (n-1)\%(k-1)=0 ，以便应对 k=2 时的情况。

如果需要统计树高，则记录一下树高即可，每次合并按照最高的树高加一进行计算

哈夫曼编码