哈夫曼思考

我们来看一个简单的问题，从小到大我们面临了很多的考试，小学-初中-高中… 然后老师对学生是如何进行区分的呢，不能说你考85他考73而让老师记住每个人的分数，而是通过一种分段的方法划分不同的学生：

if (sum < 60) {
      result = "不及格";
  } else if (sum < 70) {
      result = "及格";
  } else if (sum < 80) {
      result = "中等";
  } else if (sum < 90) {
      result = "良好";
  } else {
      result = "优秀";
  }

通过划分及格片段，就可以把数以万计的学生分为5类，老师只用知道这个学生是哪个类别就大概知道他的分数，如此就很方便管理。

我们用二叉树来展示这个判断过程如下：

image.png

我们永远是第一个判断这个学生是不是不及格，然后再去判断及格等等，那么问题来了，一个学校的学生中如果大部分都是不及格的，这个方法就很高效，但是很显然，我们大部分人应该集中在中等这个范围，所以基于此我们这个算法就有了优化的地方。

我们需要知道每个分数段都有多少人，大概是这样

image.png

肉眼可见，70-79之间的人数是最多的，所以我们最先遍历 70 的条件，很大可能第一次就找到结果而不用多次判断，所以这个优化后的二叉树应该是从根到叶子是权值逐渐变小的，所以他的思路就是从叶子开始叶子都是集中找目前最小的两个权值作为左右子树合并为一个父节点以此类推，直到找到根节点即可。

image.png

哈弗曼树思想

1.首先找到目前权值最小的两个子几点，构成一个二叉树。

image.png

2.由于A和E生成一个二叉树，其根节点的权值就会变成 A+E = 15 ，所以接下来 我们就要从 N1,B,D,C 中找到最小的两个，PS：其原理就是每次都要找最小的两个权值生成树

image.png

3.以此类推，最终这个哈弗曼树应该是这样

image.png