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

题目要求哈夫曼编码，首先要知道什么是哈夫曼编码，哈夫曼编码是一种基于哈夫曼树的编码。哈夫曼树的构成为

字符{a, b, c, d}，对应次数{1, 3, 8, 2}，如图所示：

按题目要求，需要将最小长度输出，即输出 字符的编码长度 * 字符的数量

自定义树，节点的值即为字符出现的次数

利用PriorityQueue来存储节点，每次取出节点值最小的两个节点构成新的节点并重新压入PriorityQueue中，当PriorityQueue的大小为1时，剩下的节点即为树的根节点。

当节点为叶子节点的时候，将 高度 * 节点值 累加到 count 上即可

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in  = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(in.readLine());
        PriorityQueue<HaFuManTree> queue = new PriorityQueue<>((o1,o2) -> {
            if (o1.val >= o2.val) {
                return 1;
            } else {
                return -1;
            }
        });
        String[] split = in.readLine().split(" ");
        for (String s : split) {
            queue.add(new HaFuManTree(Long.parseLong(s)));
        }
        while (queue.size() != 1) {
            HaFuManTree po1 = queue.poll();
            HaFuManTree po2 = queue.poll();
            HaFuManTree node = new HaFuManTree(po1.val + po2.val);
            node.left = po1;
            node.right = po2;
            queue.add(node);
        }
        long length = 0l;
        getSize(queue.poll(), length);
        System.out.println(count);
    }
    static long count = 0;
    public static void getSize(HaFuManTree node, long length) {
        if (node.right == null && node.left == null) {
            count += length * node.val;
        } else {
            if (node.left != null) {
                getSize(node.left, length + 1);
            }
            if (node.right != null) {
                getSize(node.right, length + 1);
            }
        }
    }
}
class HaFuManTree {
    long val;
    HaFuManTree left;
    HaFuManTree right;

    public HaFuManTree(long val) {
        this.val = val;
    }
}