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

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static class node {
        long value;
        node left;
        node right;
        int deep;// 记录深度

        public node(long value) {
            this.value = value;
            this.deep = 0;
        }

        public node(node n1, node n2, long value) {
            this.left = n1;
            this.right = n2;
            this.value = value;
        }
    }

    private node root;// 最后生成的根节点
    List<node> nodes;

    public Main() {
        this.nodes = null;
    }

    public Main(List<node> nodes) {
        this.nodes = nodes;
    }

    public void createTree() {
        Queue<node> q1 = new PriorityQueue<node>(new Comparator<node>() {
            public int compare(node o1, node o2) {
                if (o1.value > o2.value) {
                    return 1;
                } else if (o1.value == o2.value) {
                    return 0;
                } else {
                    return -1;
                }
            }
        });
        q1.addAll(nodes);
        while (!q1.isEmpty()) {
            node n1 = q1.poll();
            node n2 = q1.poll();
            node parent = new node(n1, n2, n1.value + n2.value);
            if (q1.isEmpty()) {
                root = parent;
                return;
            }
            q1.add(parent);
        }
    }

    public long getweight() {
        Queue<node> q1 = new ArrayDeque<node>();
        q1.add(root);
        long weight = 0;
        while (!q1.isEmpty()) {
            node va = q1.poll();
            if (va.left != null) {
                va.left.deep = va.deep + 1;
                va.right.deep = va.deep + 1;
                q1.add(va.left);
                q1.add(va.right);
            } else {
                weight += va.deep * va.value;
            }
        }
        return weight;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        scan.nextLine();
        String[] fStr = scan.nextLine().split(" ");
        List<node> list = new ArrayList<node>();
        for (int i = 0; i < num; i++) {
            list.add(new node(Long.parseLong(fStr[i])));
        }
        Main tree = new Main();
        tree.nodes = list;
        tree.createTree();
        System.out.println(tree.getweight());
    }
}