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

import java.util.*;
public class Main {
    static long sum = 0;
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        ArrayList<MyNode> counts = new ArrayList<>();
        for(int i = 0; i < n; i++){
            counts.add(new MyNode(input.nextInt()));
        }
        //哈夫曼编码是将字符按照其出现次数生成哈夫曼树
        //哈夫曼数的构造方式是将字符按照出现次数排序
        //然后取出两个最小值，将其合为一颗树，根节点为两值之和
        //然后将这个根节点放回去,重复上述操作
        //这样可以保证出现频率越高的字符越靠近根节点
        //然后从根节点开始遍历，每一个点，向左为0向右为1
        //将前往这个点的路径值合成一个二进制数
        //这个二进制数就是该点对应字符的哈夫曼编码
        //最后将每个字符的编码长度与出现次数相乘，再加起来就行

        //1.生成哈夫曼树
        MyNode root = createHFTree(counts);
        //2.遍历每一个字符，确定其对应哈夫曼表
        assert root != null;
        getSum(root);
        //3.得到最终结果
        System.out.println(sum);
    }

    private static void getSum(MyNode root) {
        //每个结点的编码值长度等于其深度（根节点深度从0开始算）
        Queue<MyNode> queue = new LinkedList<>();
        root.depth = 0;
        queue.offer(root);
        MyNode cur;
        while (!queue.isEmpty()){
            cur = queue.poll();
            //哈夫曼树中，一个结点要么无左无右，要么有左有右
            if(cur.left!=null){
                cur.left.depth = cur.depth+1;
                cur.right.depth = cur.depth+1;
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                sum += cur.val * cur.depth;
            }
        }
    }


    public static MyNode createHFTree(ArrayList<MyNode> counts){
        //树的创建过程中，每添加一次子树，都要排序一次，由于大致已经有序，就用优先队列（堆排序）
        PriorityQueue<MyNode> queue = new PriorityQueue<>(Comparator.comparingLong(o -> o.val));
        queue.addAll(counts);
        while (!queue.isEmpty()){
            MyNode left = queue.poll();
            MyNode right = queue.poll();
            assert right != null;
            MyNode par = new MyNode(left.val + right.val);
            par.left = left;
            par.right = right;
            if(queue.isEmpty()){
                return par;
            }else {
                queue.add(par);
            }
        }
        return null;
    }
}
class MyNode{
    long val;
    long depth;
    MyNode left;
    MyNode right;
    public MyNode(long val){
        this.val = val;
    }
}