哈夫曼编码

题目内容

题目描述

字符的编码方式有多种,除了大家熟悉的ASCII编码,哈夫曼编码(Huffman Coding)也是一种编码方式,它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码,称之为最优编码。哈夫曼编码常被用于数据文件压缩中,其压缩率通常在20%~90%之间。你的任务是对从键盘输入的一个字符串求出它的哈夫曼编码的长度。

输入描述

输入数据为一行字符串,表示要编码的字符串。 其中,字符串的长度为2~1000,每个字符都是大写字母。

输出描述

输出字符串的huffman编码长度L。

样例输入

AAAAABCD

样例输出

13

提示

用一个数组a保存所有ASCII编码出现的次数,初始为0;输入字符串后,遍历每个字符,字符的ASCII编码相应的数组a位置上的数+1。随后,维护一个按照数值大小从小到大排序的优先队列。遍历数组a,进入队列。最后,从队首开始循环这个队列,每次将队首元素和它的下一个元素出队,求出队首元素和下一个元素的和s,用一个遍历sum累加这个和,然后将这个和s进入队列,直到队列为空或者队列元素只剩下一个,输出结果sum。
提交评测
请登录后再操作

题目描述

哈夫曼编码
1449
0
08Level6
13
10
77%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在