type
status
password
date
slug
summary
category
URL
tags
icon
背景(采用不同的编码方式效率不同)
分数 | 0~59 | 60~69 | 70~79 | 80~89 | 90~100 |
人数占比 | 5% | 15% | 40% | 30% | 10% |
如上表所示，将学生的百分制成绩转换为五分制成绩。 分: ，分: ，分: ，分: ，分: 。编制一个程序，将百分制转换成五个等级输出
若考虑上述程序所耗费的时间，就会发现该程序的缺陷。在实际中，学生成绩在五个等级上的分布是不均匀的。
当学生百分制成绩的录入量很大时，上述判定过程需要反复调用，此时程序的执行效率将成为一个严重问题。例如如果学生的总成绩数据有10000条，则5％的数据需 1 次比较，15％的数据需 2 次比较，40％的数据需 3 次比较，40％的数据需 4 次比较。使用上述判断方式或者哈夫曼树的判断方式之后，两者的差别如下所示：
哈夫曼树
定义
哈夫曼（Huffman）树又称作最优二叉树，它是 个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。
- 路径：指从一个结点到另一个结点之间的分支序列。
- 路径长度：指从一个结点到另一个结点所经过的分支数目。
- 结点的权：给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。
- 带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。
- 树的带权路径长度：为树中所有叶子结点的带权路径长度之和，通常记为：
其中 表示为第 个叶子结点的权值； 表示该叶子结点到根结点的路径长度。
构造树
原则：权值越大的叶子节点越靠近根节点
假设有 个权值，则构造出的哈夫曼树有 个叶子结点。 个权值分别设为 ，哈夫曼树的构造规则为：
- 将 看成是有 棵树的森林(每棵树仅有一个结点)；
- 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
- 从森林中删除选取的两棵树，并将新树加入森林；
- 重复 2、3 步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
代码
哈夫编码(就是前缀编码)
哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。
例：如果需传送的电文为 ‘ABACCDA’，它只用到四种字符，用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00, 01,10, 11，则上述电文便为 ‘00010010101100’（共 14 位）。使用哈夫编码可以大大缩短报文的长度， A, B, C, D 的编码分别为 0, 110, 10, 111。电文 ‘ABACCDA’ 便为 ‘0110010101110’（共 13 位）。
哈夫曼树__牛客网 (nowcoder.com)
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和的最小值。