树---2.哈夫曼树

1.哈夫曼树（最优树）：

带权路径最短的树，在信息检索中很有用。（贪心算法）

路径为0结点至多1个，路径为1的节点至多2个，路径为k的节点至多2^k个。

2.哈夫曼算法：

（1）n个权值为{W1,w2,,,wn}构成n棵二叉树集合{F1，F2...Fn}；（2）选权值最小的两颗二叉树构成一颗新二叉树，更新新二叉树的权值。（3）重复2

3.哈夫曼树应用

（1）判定问题：成绩ABCDE各个等级分布不均匀，比较最少次数得到10000个学生的成绩分组

  （2）哈夫曼编码：电文传送时01编码代表不同含义，保证每个字符的编码都不是其他字符编码的前缀，使整体编码长度最短（左分支0 右分支1）

4.哈夫曼编码实现可以对应最小堆