POJ 1521 Entropy 哈夫曼树

题目大意是给出一个字符串，默认每个字符用8位二进制数（ASCII编码）表示，求以前缀不重复编码压缩后表示字符串所需的最少二进制数位数。

题目中介绍的按频率进行前缀不重复编码的压缩思路其实就是哈夫曼编码的思路，因此只需要构建出一颗哈夫曼树，然后计算原字符串节点的WPL（带权路径长度）即可。构建哈夫曼树的算法是：

1. 首先把 n 个叶子结点看做 n 棵树（仅有一个结点的二叉树），把它们看做一个森林。
2. 在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。
3. 重复第2步直到森林中只有一棵为止。此树就是哈夫曼树。

此外如果需要求具体的字符编码（即哈夫曼编码），则在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码。

7794475    IwfWcf    1521    Accepted    756K    16MS    G++    1594B    2010-10-26 23:05:44