题解 | #哈夫曼树#

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

/**
 * 哈夫曼树--北京邮电大学
 * @return
 */
int main() {
    int n;
    while (cin >> n) {
        /*
         * 定义小根堆的优先队列
         */
        priority_queue<int, vector<int>, greater<int>> nodes;
        for (int i = 0; i < n; ++i) {
            int weight;
            cin >> weight;
            nodes.push(weight);
        }
        int ans = 0;
        /*
         * 依次弹出两个权值最小的结点，求其权值之和并放入优先队列中
         */
        while (nodes.size() > 1) {
            int x = nodes.top();
            nodes.pop();
            int y = nodes.top();
            nodes.pop();
            ans += x + y;
            nodes.push(x + y);
        }
        cout << ans << endl;
    }

    return 0;
}