哈夫曼树

//写了这么多，看讨论才知道原来直接省去建立树的过程也能解决。还是大神们眼睛毒啊
//建立哈夫曼树的过程，复试考到过。
import java.util.*;
 * 哈夫曼树，第一行输入一个数n，表示叶结点的个数。
 * 需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
 */
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n=sc.nextInt();
			PriorityQueue<TreeNode>pq=new PriorityQueue<>(n,new Comparator<TreeNode>() {
				@Override
				public int compare(TreeNode o1, TreeNode o2) {
					return o1.val-o2.val;
				}
				
			});
			while(n-->0) {
				pq.add(new TreeNode(sc.nextInt()));
			}
			TreeNode root=buildTree(pq);
			//层次遍历哈夫曼树，并求和
			int sum=bfs(root);
			System.out.println(sum);
		}
	}

	private static TreeNode buildTree(PriorityQueue<TreeNode> pq) {
        //使用优先队列建立哈夫曼树妙啊
		while(pq.size()>1) {
			TreeNode left=pq.poll();
			TreeNode right=pq.poll();
			TreeNode parent=new TreeNode(left.val+right.val);
			parent.left=left;
			parent.right=right;
			pq.add(parent);
		}
		return pq.poll();
	}

	private static int bfs(TreeNode root) {
		Queue<TreeNode>queue=new LinkedList<>();
		queue.offer(root);
		int depth=-1;//不是从0开始。开始错了
		int sum=0;
		while(!queue.isEmpty()) {
			int size=queue.size();
			depth++;
			while(size-->0) {
				TreeNode node=queue.poll();
				if(node.left==null&&node.right==null)//哈夫曼树叶子结点才算入
					sum+=node.val*depth;
				if(node.left!=null)queue.offer(node.left);
				if(node.right!=null)queue.offer(node.right);
			}
		}
		return sum;
	}

	
}
class TreeNode {
	TreeNode left;
	TreeNode right;
	int val;
	public TreeNode(int val) {
		this.val=val;
	}
}			

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args)  {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()) {
			int n = scanner.nextInt(), sum = 0;
			int[] nums = new int[n];
			for(int i = 0; i < n; i++) {
				nums[i] = scanner.nextInt();
			}
			for(int i = 0; i < n - 1; i++) {
				Arrays.sort(nums, i, n);
				nums[i + 1] = nums[i] +nums[i + 1];
				nums[i] = 0;
				sum += nums[i + 1];
			}
			System.out.println(sum);
		}
	}
}

//最关键因素是哈夫曼树最小路径长度的求法，一种简单的方法是所有非叶子节点之和
//明白这个道理之后就可以不用建堆、建树
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int sum=0;
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int[] num = new int[count];
        for(int i=0;i<count;i++) {
            num[i] = in.nextInt();
        }
        Arrays.sort(num);
        if(count==1) {
            System.out.println(num[0]);
        }else if(count==2) {
            System.out.println(num[0]+num[1]);
        }else {
            for(int i=0;i<count-1;i++) {
                num[i+1]=num[i]+num[i+1];
                sum+=num[i+1];
                Arrays.sort(num,i+1,count);
            }
            System.out.println(sum);
        }
        in.close();
    }

}

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 
import java.util.Scanner; 
public class Main{ 
    static List ye =new ArrayList(); 
    static int n; 
    public static void main(String[] args){
        Scanner in = new Scanner(System.in); 
        int min1; int min2;  
        while(in.hasNext()){
            n =in.nextInt();  
            for(int i=0;in;i++){ 
                ye.add(in.nextInt());  
            } 
            int result =0;  
            while(n>1){//执行n-1次即可  
                Collections.sort(ye);  
                min1=ye.remove(0);  
                min2=ye.remove(0);  
                ye.add(min1+min2);  
                result+=min1+min2;  
                n--;  
            }
            System.out.println(result);     
        }
    }
}

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * Created by fhqplzj on 17-2-19 at 下午8:03.
 */
public class Huff {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(n);
            for (int i = 0; i < n; i++) {
                priorityQueue.add(scanner.nextInt());
            }
            int result = 0;
            while (priorityQueue.size() > 1) {
                int a = priorityQueue.poll();
                int b = priorityQueue.poll();
                result += a + b;
                priorityQueue.add(a + b);
            }
            System.out.println(result);
        }
    }
}