题目描述
字符的编码方式有多种,除了大家熟悉的ASCII编码,哈夫曼编码(Huffman Coding)也是一种编码方式,它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码,称之为最优编码。哈夫曼编码常被用于数据文件压缩中,其压缩率通常在20%~90%之间。你的任务是对从键盘输入的一个字符串求出它的哈夫曼编码的长度。
输入描述
输入数据为一行字符串,表示要编码的字符串。 其中,字符串的长度为2~1000,每个字符都是大写字母。
输出描述
输出字符串的huffman编码长度L。
样例输入
AAAAABCD
样例输出
13
提示
用一个数组a保存所有ASCII编码出现的次数,初始为0;输入字符串后,遍历每个字符,字符的ASCII编码相应的数组a位置上的数+1。随后,维护一个按照数值大小从小到大排序的优先队列。遍历数组a,进入队列。最后,从队首开始循环这个队列,每次将队首元素和它的下一个元素出队,求出队首元素和下一个元素的和s,用一个遍历sum累加这个和,然后将这个和s进入队列,直到队列为空或者队列元素只剩下一个,输出结果sum。