#include<iostream>
#include<iomanip>
using namespace std;
#define UNIT_MAX 100
template<class T>
struct hufnode{
	T weight;
	int parent;
	int lchild;
	int rchild;
};
template<class T>
class hufman_BT{
private:
	int nn;
	hufnode<T>*BT;
public:
	hufman_BT(){BT=NULL;return;}
	void creat_hufm_BT(int,T[]);
	void prt_hufm_BT();
};
template<class T>
static int Select(hufnode<T> *p,int k,int *i,int *j){
	T w;
	int n=0;
	while((n<k)&&((p+n)->parent!=-1)){
		n=n+1;
	}
	w=(p+n)->weight;
	*i=n;
	while(n<k){
		if((((p+n)->weight)<w)&&((p+n)->parent==-1)){
			*i=n;
			w=(p+n)->weight;
		}
		n=n+1;
	}
	n=0;
	while((n<k)&&((p+n)->parent!=-1)||(n==(*i)))
		n=n+1;
	w=(p+n)->weight;
	*j=n;
	while(n<k){
		if(((p+n)->weight<w)&&(n!=(*i))&&((p+n)->parent==-1)){
			*j=n;
			w=(p+n)->weight;
		}
		n=n+1;
	}
	if((*i)>(*j)){
		n=(*i);
		(*i)=(*j);
		*j=n;
	}
	return 0;
}

template<class T>
void hufman_BT<T>::creat_hufm_BT(int n,T w[]){
	hufnode<T> *p;
	int k,i,j,m;
	nn=n;
	m=2*nn-1;
	BT=new hufnode<T>[m];
	p=BT;
	for(k=0;k<m;k++){
		(p+k)->parent=-1;
		(p+k)->lchild=-1;
		(p+k)->rchild=-1;
	}
	for(k=0;k<n;k++)
		(p+k)->weight=w[k];
	for(k=n;k<m;k++){
		Select(p,k,&i,&j);
		(p+i)->parent=k;
		(p+j)->parent=k;
		(p+k)->lchild=i;
		(p+k)->rchild=j;
		(p+k)->weight=(p+i)->weight+(p+j)->weight;
	}
	char** HC;
	HC=new char* [sizeof(n)];
	char *cd;
	int c;
	int f;
	int start;
	cd=new char[n*sizeof(char)];
	cd[n-1]='\0';
	for(i=0;i<n;++i){
		start=n-1;
		for(c=i,f=p[i].parent;f!=-1;c=f,f=p[f].parent){
			if(p[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		}
		HC[i]=new char[(n-start)*sizeof(char)];
		strcpy(HC[i],&cd[start]);
		puts(HC[i]);
	}
	free(cd);
	return;
}


/*int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
	unsigned start;
	unsigned c;
	unsigned f;
	int i;
	int m;
	int s1;
	int s2;
	char *cd;
	HuffmanTree p;
	if(n<=1)
		return 0;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用
	for(p=HT+1,i=1;i<=n;++i,++p,++w){
		(*p).weight=*w;
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	for(;i<=m;++i,++p){
		(*p).weight=0;
        (*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	for(i=n+1;i<=m;++i){
		Select(HT,i-1,&s1,&s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	cd=(char*)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for(i=1;i<=n;++i){
		start=n-1;
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
			if(HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		}
		HC[i]=(char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
	}
	free(cd);
	return 0;
}*/
/*template<class T>
void hufman_BT<T>::prt_hufm_BT(){
	hufnode<T> *p;
	int k;
	p=BT;
	cout<<"k"<<setw(7)<<"Weight"<<setw(7)<<"Parent"
		<<setw(7)<<"Lchild"<<setw(7)<<"Rchild"<<endl;
	for(k=0;k<2*nn-1;k++)
		cout<<k<<setw(7)<<(p+k)->weight<<setw(7)<<(p+k)->parent
		<<setw(7)<<(p+k)->lchild<<setw(7)<<(p+k)->rchild<<endl;
	return;
}*/
int main(){
	int *w;
	int n;
	cout<<"請輸入權值的個數:";
	cin>>n;
	cout<<"權值依次為:";
	w=new int[n];
	for(int i=0;i<n;i++)
		cin>>w[i];
	hufman_BT<int> b;
	cout<<"哈夫曼編碼如下:"<<endl;
	b.creat_hufm_BT(n,w);
	return 0;
}