霍夫曼编码，简单解析

真想爆粗口， 每次学会了霍夫曼编码，过几天就忘记， 然后又得重新学习， 我自己写博客，写自己的理解， 下次看一眼就会。印象还深刻！

借鉴https://www.cnblogs.com/-citywall123/p/11297523.html

霍夫曼编码简单原理： 就是用最少位数的二进制给 出现概率最高的字符 进行编码， 相反，出现频率低的用较多位数编码， 使得总体的编码长度大幅度减少。

如 一组字符中A,B,C,D,E 出现的次数从高到底分别为5,4,3,2,1，  A出现5次， 所以尽量用最少位数进行编码。

霍夫曼树的构造： 最大堆进行构造， 即根节点大于左右节点， 右节点大于左节点

构造霍夫曼树特点： 左节点<右节点， 左叉权重为0， 右叉权重为1.

列表lis=[5,4,3,2,1], 首先从列表中选取两个最小的（1,2）进行对比，剩余节点为lis=[5,4,3]，小的（1）为左节点（叉权重为0）， 大的（2）为右节点（叉权重为1）

， 其根节点为两个节点之和， 为1+2=3,将3 加入原来的列表中.列表为[5,4,3,3], 其中1,2,3构成一个子树， 3为1,2的父节点，1,2两点处于同等层次/深度，只是左右之分。

继续重复此步骤： 选取最小的两个点3,3， 剩余为lis=[5,4]这两个点处于同等层次/树的深度，只是左右之分，3,3之和为6， 则6为父节点， 加入列表[5,4,6]

继续重复步骤：选取最小的两个节点[4,5], 剩余lis=[6], 4,5之和为9，加入列表中lis=[6,9], 6,9处于同一深度。则6为左节点， 9 为右节点。其父节点为6+9=15

最终霍夫曼树为：

替换为原来的字符。

所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010

哈夫曼编码的带权路径权值：叶子节点的值 * 叶子节点的高度（根节点为0）

上图的带权路径长度为：（3+4+5）*2+（1+2）*3=33