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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.PriorityQueue;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static long minLen;
    public static class TreeNode {
        long count;
        TreeNode left;
        TreeNode right;

        public TreeNode(long count, TreeNode left, TreeNode right) {
            this.count = count;
            this.left = left;
            this.right = right;
        }
    }
    //构建哈夫曼树
    public static TreeNode buildHuffmanTree(PriorityQueue<TreeNode> queue) {
        TreeNode root1, root2;
        while (queue.size() > 1) {
            root1 = queue.remove();
            root2 = queue.remove();
            queue.add(new TreeNode(root1.count + root2.count, root1, root2));
        }
        return queue.remove();
    }

    //遍历赫夫曼树获取所有叶子节点的赫夫曼编码长度
    public static void calLen(TreeNode root, int len) {
        //递归实现
        if (root.left == null && root.right == null) {
            minLen += len * root.count;
            return;
        }
        //完全二叉树
        assert root.left != null;
        calLen(root.left, len + 1);
        calLen(root.right, len + 1);
    }
    public static StreamTokenizer myReader() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        return new StreamTokenizer(br);
    }

    public static void main(String[] args) throws IOException,ArithmeticException {
        StreamTokenizer st = myReader();
        st.nextToken();
        int n = (int)st.nval;
        PriorityQueue<TreeNode> queue = new PriorityQueue<>(n, (a,
                b)-> Math.toIntExact((a.count - b.count)%1000000007));
        for (int i = 0 ; i < n; i++) {
            st.nextToken();
            long count = (int)st.nval;
            queue.add(new TreeNode(count, null, null));
        }
        TreeNode root = buildHuffmanTree(queue);
        calLen(root, 0);
        System.out.println(minLen);
    }
}