哈夫曼树

是一颗二叉树，又称为最优二叉树。它的叶子节点到根节点的带权路径和最小

在这里，带权路径=一个节点的权值*该节点到另一个节点的边的数量

构建哈夫曼树

给定\(n\)个权值为\(w\)的节点

我们在其中选出权值最小的两个点取出，假设为\(w_i,w_j\)，然后再新建一个权值为\(w_i+w_j\)的节点重新放入

反复直到剩下一个节点，一棵树就好了

显然，大的节点在上面，小的节点在下面，正确性不难证明

哈夫曼编码

假设我们有一个字符串IAKIOI

这个字符串的总bit数为48，我们能不能把它压缩一下呢？

哈夫曼编码就是一种无损压缩方法，它的思想是：出现频率越少的字符编码越短，频率越高字符编码越长

实现

我们结合上面的哈夫曼树，将每种字符出现的次数当做该字符的权值，构建一颗哈夫曼树

然后对于每一棵子树，左边为0， 右边为1，叶子节点到根的路径就是它的哈夫曼编码

我们又可以发现，压缩后的字符串的长度就是上图中的蓝色节点的权值和

这是因为在不断合并的过程中，有一些节点的权值不断地相加。

然后再将它们加起来，答案就出来了

例题

TODO: HDU1053 entropy
TODO: 洛谷 荷马史诗

哈夫曼树和哈夫曼编码

原文：https://www.cnblogs.com/zhangwenxuan/p/15112611.html