7-2 哈夫曼树与哈夫曼编码

哈夫曼树(Huffman Tree)又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
本题要求从键盘输入若干电文所用符号及其出现的频率，然后构造哈夫曼树，从而输出哈夫曼编码。
注意：为了保证得到唯一的哈夫曼树，本题规定在构造哈夫曼树时，左孩子结点权值不大于右孩子结点权值。如权值相等，则先选优先级队列中先出队的节点。编码时，左分支取“0”，右分支取“1”。

输入格式:

输入有3行。 第1行：符号个数n（2～20）。 第2行：一个不含空格的字符串。记录着本题的符号表。我们约定符号都是单个的小写英文字母，且从字符‘a’开始顺序出现。也就是说，如果 n 为 2 ，则符号表为 ab ；如果 n 为 6，则符号为 abcdef；以此类推。 第3行：各符号出现频率（用乘以100后的整数），用空格分隔。
输出格式:

先输出构造的哈夫曼树带权路径长度。 接下来输出n行，每行是一个字符和该字符对应的哈夫曼编码。字符按字典顺序输出。字符和哈夫曼编码之间以冒号分隔。

例如：

a:10

b:110
输入样例:

在这里给出一组输入。例如：

8
abcdefgh
5 29 7 8 14 23 3 11

输出样例:

在这里给出相应的输出。例如：

271
a:0001
b:10
c:1110
d:1111
e:110
f:01
g:0000
h:001

提示： 以上示例数据，按题目要求建立的Haffman Tree如下图：

用堆构建即可,每次把堆内权值最小两个取出来合并成一个节点即可
当堆里只剩一个节点时就是huffman根节点

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;

char buf[MAXN];

struct Node {
	Node* lef;
	Node* rig;
	int w;
	char ch;
	int cnt;
	Node(int _w=0, char _ch=0) : lef(0), rig(0), w(_w), ch(_ch), cnt(1) { }
} ;

struct cmp {
	bool operator()(const Node* x, const Node* y) const {
		if(x->w == y->w) return x->cnt > y->cnt;
		return x->w > y->w;
	}
} ;

map<char, string> mp;
int sum;
void dfs(Node* now, string str, int level) {
	if(!now) return ;
	if(!now->lef && !now->rig) {
		mp[now->ch] = str;
		sum += level*now->w;
		return ;
	}
	dfs(now->lef, str+'0', level+1);
	dfs(now->rig, str+'1', level+1);
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%d %s ", &n, buf+1);
	priority_queue<Node*, vector<Node*>, cmp> q;
	for(int i=1, w; i<=n; i++) {
		scanf("%d ", &w);
		q.push(new Node(w, buf[i]));
	}
#if 0
	while(!q.empty()) {
		auto ptr = q.top();
		printf("%c %d\n", ptr->ch, ptr->w);
		q.pop();
	}
	return 0;
#endif
	while(q.size()-1) {
		Node* lef = q.top(); q.pop();
		Node* rig = q.top(); q.pop();
		Node* root = new Node(lef->w + rig->w);
		root->lef = lef, root->rig = rig;
		root->cnt = lef->cnt + rig->cnt + 1;
		q.push(root);
	}
	dfs(q.top(), "", 0);
	printf("%d\n", sum);
	for(auto it : mp)
		printf("%c:%s\n", it.first, it.second.data());


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}