贪心算法 - 哈夫曼编码 Huffman
哈夫曼编码：
一种字符编码方式，常用于数据文件压缩。压缩率通常在20%~90%。
主要思想：
采取可变长编码方式，对文件中出现次数多的字符采取比较短的编码，对于出现次数少的字符采取比较长的编码，可以有效地减小总的编码长度。
例如，在英文中，e的出现频率最高，z的出现频率最低，所以可以用最短的编码来表示e，用最长的编码表示z。
例子：
一个文件包含100 000个字符，且仅含有a,b,c,d,e,f六个字符，那么可以用3位bit来编码这六个字符，称之为定长码。
那么采取定长码共需要的位数为 3* 100 000 = 600 000位。
这六个字符出现的频率如图所示，a最多，f最少。因此如果采取图中所示的变长码，所需要的位数为：
(45*1 + 13*3 + 12 * 3 + 16*3 + 9*4 + 5*4) * 1000 = 224 000。
可以看出压缩了25%，a的编码长度最短，为一位，f的编码长度最长，为4位。
前缀码：
当读取文件时，对于定长码文件，已经知道了每个字符的编码长度，所以只需按部就班的一个一个的读取字符即可；
对于变长码文件，各个字符的编码长度不一，因此需要小心设计各个字符的编码，一面混淆。
比如，如果a的编码为0，b的编码为01，c的编码为1，那么解码的时候如果遇到‘001’，则既可以解码成‘aac’，也可以解码成‘ab’。
因为b的编码中包含了a的编码，也就是a的编码是b的编码的前缀。
所以，变长码编码的设计，每个字符的编码都不能是其他字符编码的前缀，这种方式称之为前缀码。
可以用二叉树来表示每个字符的编码，以左为0，以右为1，这样每个叶子节点的路径均不同，也都不会称为其他叶子节点的前缀。
这样每个叶子节点的路径，就是每个字符的编码。
图中形成的编码与表格中的有些差异，但是各个字符编码的长度都相同，这是左子树和右子树的区别，但是对编码长度没有影响。
代码实现：
f+e : 5.0+9.0 = 14.0c+b : 12.0+13.0 = 25.0#+d : 14.0+16.0 = 30.0#+# : 25.0+30.0 = 55.0a+# : 45.0+55.0 = 100.0a : 0b : 101c : 100d : 111e : 1101f : 1100z+q : 0.074+0.095 = 0.16899999999999998x+j : 0.15+0.153 = 0.303#+# : 0.16899999999999998+0.303 = 0.472#+k : 0.472+0.772 = 1.244v+# : 0.978+1.244 = 2.222b+p : 1.492+1.929 = 3.4210000000000003y+g : 1.974+2.015 = 3.989#+f : 2.222+2.228 = 4.45w+m : 2.36+2.406 = 4.766u+c : 2.758+2.782 = 5.54#+# : 3.4210000000000003+3.989 = 7.41l+d : 4.025+4.253 = 8.278#+# : 4.45+4.766 = 9.216000000000001#+r : 5.54+5.987 = 11.527000000000001h+s : 6.094+6.327 = 12.421n+i : 6.749+6.966 = 13.715#+o : 7.41+7.507 = 14.917a+# : 8.167+8.278 = 16.445t+# : 9.056+9.216000000000001 = 18.272#+# : 11.527000000000001+12.421 = 23.948e+# : 12.702+13.715 = 26.417#+# : 14.917+16.445 = 31.362000000000002#+# : 18.272+23.948 = 42.22#+# : 26.417+31.362000000000002 = 57.779#+# : 42.22+57.779 = 99.999a : 1110b : 110000c : 01001d : 11111e : 100f : 00101g : 110011h : 0110i : 1011j : 001001011k : 0010011l : 11110m : 00111n : 1010o : 1101p : 110001q : 001001001r : 0101s : 0111t : 000u : 01000v : 001000w : 00110x : 001001010y : 110010z : 001001000
关于MinHeap的代码实现，请参考前一篇文章：贪心算法 - 最小生成树 Kruskal算法
