最佳编码 ---哈夫曼树 优先队列

Problem Description
文本编码是计算机通信中的常见问题。
以文本“AAAAABCD”为例，如果使用ASCII，则一共需要64位（因为每个字符的ASCII编码都是需要8位）。
对应的，如果我们将A编码为“00”，“B”为“01”，“C”为“10”，“D”为“11”，那么我们可以只编码16位; 得到的位模式将是“0000000000011011”。然而，这仍然是一种固定长度的编码。
由于字符“A”的出现频率较高，我们是否可以通过用较少的位对它进行编码来获得更好的效果？
事实上，我们确实可以。
最佳编码是将“A”标记为“0”，“B”标记为“10”，“C”标记为“110”，“D”标记为“111”。（显然，这不是唯一的最佳编码，因为很显然，对B，C和D可以自由交换，而不增加最终编码的大小。）
使用这种编码，上述的字符串仅需要13位，编码为“0000010110111”，相对ASCII编码方案，压缩比为4.9比1。通过从左到右读取该编码，您会发现，无前缀编码可以很容易地将其解码为原始文本，即使代码具有不同的位长度。

Input
输入包含多组文本字符串，每行一个。
文本字符串将只包含大写字母、数字字符和下划线（用于代替空格）。
单词“END”表示输入结束，不做处理。

Output
对于输入中的每个文本字符串，输出8位ASCII编码的长度、最佳编码的长度，以及对应的压缩率比值，压缩比精确到小数点后一位。

Sample Input
AAAAABCD
THE_CAT_IN_THE_HAT
END

Sample Output
64 13 4.9
144 51 2.8

#include<bits/stdc++.h>
using namespace std;

string str;
int len, num[30];

int bfs() {
	priority_queue<int, vector<int>, greater<int> > q;  // 创建优先队列，从小到大排序
	for(int i = 0; i < 30; i++) {
		if(num[i])	q.push(num[i]);  // 放入每个字母的个数
	}
	int sum = 0;
	if(q.size() == 1)	sum = q.top();  // 如果只有一个字母，直接等于该字母的数量
	while(q.size() > 1) {  // 得到前两个最小的叶子节点，将和放入队列中
		int a = q.top();	q.pop();
		int b = q.top();	q.pop();
		sum += (a + b);	    q.push(a + b);   // 因为ans累加了之前的值，所以传入的是a  + b而非ans;
	}
	return sum;
}

int main() {
	while(cin >> str) {
		memset(num, 0, sizeof num);
		if(str == "END")	break;  // 注意为双引号
		len = str.size();  // 得到string类型的长度
		for(int i = 0; i < len; i++) {
			if(str[i] == '_')	num[26]++;  // 应为'A' - 'A'等于0，从下标0开始，所以'_'就在num[26]
			else	num[str[i] - 'A']++;
		} 
		int res = bfs();
		printf("%d %d %.1lf\n", len * 8, res, len * 8.0 / res);
	}
	return 0;
}