浅谈Huffman树

浅谈Huffman树"/>

浅谈Huffman树

学习ing

二叉哈夫曼树

一、定义

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。（摘自百度百科）

带权路径：到达该叶子节点经过的边数×叶子节点当前代表的数

二、实现

贪心

每次从所给序列中找到两个权值最小的点合并，将合并后的新权值放回序列中，然后反复操作，直到序列中只剩下一个元素。（用堆实现）

三、正确性

因为每次都选择的是权值最小的点先合并，最后构成的一个树中这些点一定是位于树中深度最大的地方。

四、性质

按照这个方法构造出来的哈夫曼树满足每个编码都不会是其他编码的左起子串（可以理解为前缀）
因为从根到该叶子结点构成一个编码，中途不会存在其他编码

例题：NOIP 2004 合并果子

k叉哈夫曼树

一、定义

和二叉哈夫曼树没什么区别。

二、实现

1.将二叉哈夫曼树中每次选两个值最小的，改为每次选前k个最小的即可
2.只有满的k叉哈夫曼树构造出来才是最优的。不满足的，就补充0构造为满的k叉哈夫曼树。若序列中有n个数，现在要求构造k叉哈夫曼树，如果满足 ( n − 1 ) % ( k − 1 ) = = 0 (n-1)\%(k-1)==0 (n−1)%(k−1)==0则为满的（因为每取k个出来，就会放回一个，相当于取走（k-1）个，而最后我们还需要剩一个（n-1的来源））
e.g三叉哈夫曼树：1 2 3 4，先取最小的三个数1 2 3 就合并成6，然后再合并6 4，得到答案16。但是先合并1 2,成3，再合并3 3 4这样代价最小

例题 NOI 2015 荷马史诗