哈夫曼编码&哈夫曼树
[toc]
前置芝士
WPL
$所有叶子节点的权值*路径长度(深度)$
$WPL = \sum_{i=1}^nl_iw_i$。
e.g. 如图为一颗二叉树$T$
它的$WPL=9*3+(16+17)4+52+3+1$
显然有一个性质: $WPL$=所有非叶子节点权值的和
哈夫曼树
1.定义
$WPL$最小的二叉树
上面的$T$即为一颗哈夫曼树
2.构造原则
权值越大越靠近根节点
3.构造过程
贪心算法,用优先队列,每次取出权值最小和次小的两项,作为叶子节点构造一棵二叉树。
演示:
第一步
第二步
第三步
第四步
4.代码实现
|
|
5.练习题
题意
建造一颗k叉哈夫曼树,并输出它的$WPL$,以及它的高度$h$
代码
|
|
哈夫曼编码(初赛知识)
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。在电讯通信业务中,通常用二进制编码来表示字母或其他字符,并用这样的编码来表示字符序列。
参考
BV1hK4y1k7Wr