3531.哈夫曼树

caution

原题链接：https://www.acwing.com/problem/content/description/3534/

思路

根据哈夫曼树的定义，要找到一个序列当中最小和次小的，然后累加之后再放回序列。直接可以用优先队列（小根堆）实现。

带权路径就是每次累加之和。

代码

#include <bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>, greater<int>> heap;

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;
        heap.push(x);
    }

    int res = 0;

    while (heap.size() > 1) {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        int sum = a + b;
        res += sum;
        heap.push(sum);
    }
    cout << res << endl;
    return 0;
}