哈夫曼树
是一颗二叉树，又称为最优二叉树。它的叶子节点到根节点的带权路径和最小
在这里，带权路径=一个节点的权值*该节点到另一个节点的边的数量
构建哈夫曼树
给定\(n\)个权值为\(w\)的节点
我们在其中选出权值最小的两个点取出，假设为\(w_i,w_j\)，然后再新建一个权值为\(w_i+w_j\)的节点重新放入
反复直到剩下一个节点，一棵树就好了
显然，大的节点在上面，小的节点在下面，正确性不难证明
哈夫曼编码
假设我们有一个字符串IAKIOI
这个字符串的总bit数为48，我们能不能把它压缩一下呢？
哈夫曼编码就是一种无损压缩方法，它的思想是：出现频率越少的字符编码越短，频率越高字符编码越长
实现
我们结合上面的哈夫曼树，将每种字符出现的次数当做该字符的权值，构建一颗哈夫曼树
然后对于每一棵子树，左边为0， 右边为1，叶子节点到根的路径就是它的哈夫曼编码
我们又可以发现，压缩后的字符串的长度就是上图中的蓝色节点的权值和
这是因为在不断合并的过程中，有一些节点的权值不断地相加。
然后再将它们加起来，答案就出来了
例题
TODO: HDU1053 entropy
TODO: 洛谷 荷马史诗