题解 | 哈夫曼树，巨通俗易懂，简洁高效

#include <iostream>
#include <queue>
using namespace std;

// 自定义比较函数，用于优先队列（最小堆）
struct myCompare {
    bool operator()(const int& a, const int& b) {
        return a > b;
    }
};

int main() {
    int n;
    while (cin >> n) { // 处理多组数据
        priority_queue<int, vector<int>, myCompare> minHeap; // 最小堆
        int weight;
        for (int i = 0; i < n; i++) {
            cin >> weight;
            minHeap.push(weight); // 将叶节点权值插入最小堆
        }

        int totalCost = 0; // 总权值
        while (minHeap.size() > 1) {
            // 取出两个最小的权值
            int min1 = minHeap.top();
            minHeap.pop();
            int min2 = minHeap.top();
            minHeap.pop();

            // 合并两个节点，计算新节点的权值
            int sum = min1 + min2;
            totalCost += sum; // 累加到总权值
            minHeap.push(sum); // 将新节点插入最小堆
        }

        cout << totalCost << endl; // 输出结果
    }
    return 0;
}