java兑现哈夫曼树模板

package Template;


public class HuffmanTree {
	class HuffmanNode {
		int w;// 权值
		int lChild, rChild, parent;// 左右孩子及父节点

		public HuffmanNode(int w) {
			this.w = w;
			lChild = rChild = parent = -1;
		}
	}

	int n;
	HuffmanNode[] huffman ;

	//从huffman中找出两个最小的权值，并保存小标到m1和m2
	int m1,m2;
	public void selectMin(){
		//找出最小的
		int minw = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			if (huffman[i].w < minw && huffman[i].parent == -1) {
				minw = huffman[i].w;
				m1 = i;
			}
		}
		//找次小的
		minw = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			if (huffman[i].w < minw && huffman[i].parent == -1 && i != m1) {
				minw = huffman[i].w;
				m2 = i;
			}
		}
	}
	
	//建立赫夫曼树
	public void buildHuffmanTree(int[] w) {
		n = w.length;
		huffman = new HuffmanNode[2*n-1];
		
		for (int i = 0; i < n; i++)
			huffman[i] = new HuffmanNode(w[i]);
		for (int i = n; i < 2 * n - 1; i++)
			huffman[i] = new HuffmanNode(-1);
		
		while(n < huffman.length){
			//从huffman中选择两个权值最小的节点构建新节点
			selectMin();
			//构造新节点
			huffman[n].w =  huffman[m1].w+huffman[m2].w;
			huffman[n].lChild = m1;
			huffman[n].rChild = m2;
			//修改m1和m2的父节点指针
			huffman[m1].parent = n;
			huffman[m2].parent = n++;
			
		}

	}
	//求带权路径长度
	public int WPL(int[]w){
		int sum = 0;
		for(int i = 0;i<w.length;i++){
			int p = huffman[i].parent;
			int ans = 0;
			while(p != -1){
				ans ++;
				p = huffman[p].parent;
			}
			sum  +=ans*w[i]; 
		}
		return sum;
	}
	//测试
	public void test(){
		int []w = {7,5,2,4};
		buildHuffmanTree(w);
		int r = WPL(w);
		System.out.println(r);
	}

	public static void main(String[] args) {
		new HuffmanTree().test();
	}

}