一、实际问题场景
比如要为学生的成绩按照分数线分为优、良、中、及格、和不及格，对应的分数线如下：
| 等级 | 优 | 良 | 中 | 及格 | 不及格 |
|---|---|---|---|---|---|
| 分数区间 | 90-100 | 80-89 | 70-79 | 60-69 | 0-59 |
| 分数在该区间的概率 | 10% | 30% | 40% | 10% | 10% |
现在有大量的学生的成绩需要对比，如果按照下面两种顺序进行比较：由于不同分数段的概率不一样，因此不同的比较顺序需要比较的次数不一样，所需时间也就不一样了：(如对于大概率的分数75，图一比较了3次。而图二比较2
次)
因此为了得到最少的比较次数，就需要一种方法得到最优的比较顺序，即赫夫曼树。
二、赫夫曼树
概念：
路径长度：节点到节点之间的路径数
带权路径长度：节点上的权数与路径长度的乘机。
分析：
下图的带权路径长度=10+2x10+3x40+4x30+4x10=310,显然按照这个概率和这种比较方式，100个成绩需要比较310次。因此问题就在于获得最小的带权路径长度。
构造赫夫曼树：
注：为方便表示，将优、良、中、及格、和不及格命名为A、B、C、D、E。
- 将有权值的节点排序：A-10，B-30，C-40，D-10，E-10；
- 将最小权值的两个节点A-10、D-10作为新节点AD-20的左右孩子，权值小的作为左孩子，大的作为右孩子。并将新的节点AD与剩下的比较，并重复上述过程，直到只剩两个节点为止。
- 过程如下:
- A-10，B-30，C-40，D-10，E-10；
- E-10，AD-20，B-30，C-40；
- EAD-30，B-30，C-40；
- C-40，BEAD-60；
- 逆向上述过程，得到赫夫曼树(注意左子树或左孩子为权值小的)：
- 计算：带权路径长度=40+30x2+10x2+10x3+10x3=130,这时如果有100个数据，仅需要比较130次即可。
- 代码转换：
1
2
3
4
5
6
7
8
9
10
11
12
13char getGread(int score)
{
if(score >=70 && score <= 79)
return 'C';
else if(score >=80 && score <= 89)
return 'B';
else if(score >=0 && score <= 59)
return 'E';
else if(score >=90 && score <= 100)
return 'A';
else
return 'D';
}
...
...
00:00
00:00
本文为作者原创文章，未经作者允许不得转载。