题解 | #【模板】哈夫曼编码#

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<MyNode> list = new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(new MyNode((long)sc.nextInt()));
        }
        //生成哈夫曼树
        MyNode root = createHFTree(list);        
        System.out.println(getSum(root));
    }
    public static long getSum(MyNode root){
        long sum = 0;
        Queue<MyNode> queue = new LinkedList<>();
        root.depth = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            MyNode node = queue.poll();
            if(node.left!=null){
                node.left.depth = node.depth+1;
                node.right.depth = node.depth+1;
                queue.add(node.left);
                queue.add(node.right);
            }else{
                sum+=node.val*node.depth;
            }
        }
        return sum;


    }
    public static MyNode createHFTree(List<MyNode> list){
        //创建哈夫曼树过程中，每添加一次节点，都要排序一次，就用优先队列（堆排序）
        PriorityQueue<MyNode> queue = new PriorityQueue<>(Comparator.comparingLong(o -> o.val));
        queue.addAll(list);
        while(!queue.isEmpty()){
            MyNode left = queue.poll();
            MyNode right = queue.poll();
            if(right == null) //堆中只有一个节点，那就是根节点
                return left;
            MyNode newNode = new MyNode(left.val+right.val);
            newNode.left = left;
            newNode.right = right;
            queue.add(newNode);

        }
        return null;
    }
}

class MyNode{
    long val;
    long depth;
    MyNode left;
    MyNode right;
    public MyNode(long val){
        this.val = val;
    }

}