输入字符集出现的概率/频次，输出对应的哈夫曼编码。
（ Ctrl + Z 回车结束输入 ）
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN=2048;
struct huff{
// char c;
double weight;
huff* left;
huff* right;
huff() {
left=NULL, right=NULL;
}
};
struct cmp{
bool operator()(huff* a, huff* b) {
return a->weight > b->weight;
}
};
priority_queue<huff*, vector<huff*>, cmp> que;
int code[MAXN], cur=0;
int DFS(huff* h) {
if(h->left==NULL && h->right==NULL) {
printf("%.3lf -> ", h->weight);
for(int i=0;i<cur;i++)
printf("%d", code[i]);
return puts("");
}
code[cur++] = 0;
DFS(h->left);
cur--;
code[cur++] = 1;
DFS(h->right);
cur--;
return 0;
}
int main() {
double w;
while(~scanf("%lf", &w)) {
huff* h = new huff();
h->weight = w;
que.push(h);
}
while(que.size()>1) {
huff* h1 = que.top();
que.pop();
huff* h2 = que.top();
que.pop();
huff* h = new huff();
h->left = h1; h->right = h2; h->weight = h1->weight + h2->weight;
que.push(h);
}
huff* root = que.top();
DFS(root);
return 0;
}
示例输入：0.1 0.15 0.2 0.25 0.3
示例输出：
0.200 -> 00
0.250 -> 01
0.100 -> 100
0.150 -> 101
0.300 -> 11
