蓝桥杯04---Huffuman树

        哈夫曼树又是最优二叉树，它的度为2（几个孩子），因此可以推算出它的总元素个数为2n-1。用数组法时可以由此确定出初始化元素个数。

        解决方法为：先排序，再选择两个最小的数相加，结果放在队尾，然后删除用掉的这两个数。循环此操作，直至剩下最后一个数即可。

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

public class Main {
    //用队列构造哈夫曼树
    public static void main(String[] args) {
        //1.初始化数组队列，输入数据
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//个数
        //哈夫曼树的度为2，加上根节点，所以总数为2n+1
        if(n>0&&n<=100){
            int[] queueArr=new int[2*n-1];
            for(int i=0;i 
2.2集合法 
import java.util.*;

public class Demo22 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        if(n<=100){
            List list=new ArrayList();
            for(int i=0;i1){
                Collections.sort(list);
                int min1= (int) list.get(0);
                int min2= (int) list.get(1);
                list.remove(0);
                list.remove(0);
                list.add(min1+min2);
                sum=sum+min1+min2;
            }
            System.out.println(sum);

        }
    }
}
 
2.3运行测试 
 
        可见两者运行时间和空间相差不多，论代码量和逻辑思路，还是集合比较方便。
 
ps:Arrays.sort(queueArr,front,rear+1);参数一为数组名，参数二为起始位置（不含本身），参数为结束位置（含）。