class HTNode{
	public int weight;
	public int parent,lchild,rchild;
	
	public HTNode(int weight) {
		this.weight=weight;
		this.parent=0;
		this.lchild=0;
		this.rchild=0;
	}
	
	@Override
	public String toString() {
		return "(w:"+this.weight+",l:"+this.lchild+",r:"+this.rchild+",p:"+this.parent+")";
	}
}

public class 例6_6_2 {
	
	public static HTNode[] huffmanTreeBuild(int[] w){
		if(w.length<=1)return null;
		int m=2*w.length-1;
		HTNode[] ht=new HTNode[m];
		for (int i = 0; i < w.length; ++i) {
			ht[i]=new HTNode(w[i]);
		}
		
		for (int i = w.length; i < m; ++i) {
			ht[i]=new HTNode(0);
		}
		
		for (int i = w.length; i < m; ++i) {
			int[] spc=select(ht,i);
			ht[spc[0]].parent=i;
			ht[spc[1]].parent=i;
			
			if(ht[spc[1]].lchild==0 && ht[spc[1]].rchild==0){
				ht[i].lchild=spc[1];
				ht[i].rchild=spc[0];
			}else{
				ht[i].lchild=spc[0];
				ht[i].rchild=spc[1];
			}
			
			ht[i].weight=ht[spc[0]].weight+ht[spc[1]].weight;
		}
		return ht;
	}
	
	public static String[] huffmanTree(HTNode[] ht,int n){
		String[] hc=new String[n];
		for (int i = 0; i < n; i++) {
			String cd="";
			for (int c = i,f=ht[i].parent; f != 0; c=f,f=ht[f].parent) {
				if(ht[f].lchild==c){
					cd=0+cd;
				}else{
					cd=1+cd;
				}
			}
			hc[i]=ht[i].weight+":"+cd;
		}
		return hc;
	}
	
	public static String[] huffmanTree2(HTNode[] ht,int n){
		String[] hc=new String[n];
		int p,m;
		m=2*n-1;
		p=m-1;
		for (int i = 0; i < n; i++) {
			hc[i]=ht[i].weight+":";
		}
		for (int i = 0; i < m; i++) {
			ht[i].weight=0;
			if(ht[i].lchild==0 && ht[i].rchild==0){
				ht[i].lchild=-1;
				ht[i].rchild=-1;
			}
		}
		
		String cd="";
		while(p>=0){
			if(ht[p].weight==0){
				ht[p].weight=1;
				if(ht[p].lchild >= 0){
					p=ht[p].lchild;
					cd+="0";
				}else if(ht[p].rchild<0){
					hc[p]+=cd;
				}
			}else if(ht[p].weight==1){
				ht[p].weight=2;
				if(ht[p].rchild>=0){
					p=ht[p].rchild;
					cd+="1";
				}
			}else{
				ht[p].weight=0;
				p=ht[p].parent;
				
				
				
				if(cd.length()==0){
					break;
				}
				cd=cd.substring(0,cd.length()-1);
			}		
		}
		return hc;
	}
	
	public static String[] huffmanTree(int[] w){
		return huffmanTree(huffmanTreeBuild(w), w.length);
	}

	private static int[] select(HTNode[] ht, int i) {
		int min1=Integer.MAX_VALUE;
		int min2=Integer.MAX_VALUE;
		int[] scp={0,0};
		
		for (int j = 0; j < i; j++) {
			if(ht[j].parent>0)continue;
			if((min1>ht[j].weight) || (min1==ht[j].weight && ht[j].rchild==0 && ht[j].lchild==0)){
				if((min1<min2) || (min1==min2 && ht[scp[0]].rchild==0 && ht[scp[0]].lchild==0) ){
					scp[1]=scp[0];
					min2=min1;
				}
				scp[0]=j;
				min1=ht[j].weight;
			}else if((min2>ht[j].weight) || (min2==ht[j].weight && ht[j].lchild==0 && ht[j].rchild==0)){
				scp[1]=j;
				min2=ht[j].weight;
			}
		}
		
		return scp;
	}
	
	public static void main(String[] args) {
		int[] w=new int[]{5,29,7,8,14,23,3,11};
		String[] str=huffmanTree(w);
		String[] str2=huffmanTree2(huffmanTreeBuild(w),w.length);
		
		for (String string : str) {
			System.out.println(string);
		}
		
		for (String string : str2) {
			System.out.println(string);
		}
	}
}