题解 | #哈夫曼树#

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

int main(){
    int n,m;
    priority_queue<int, vector<int>, greater<int> > myPrioQueue;
    while(cin>>n){
        for(int i = 0; i < n; i++){
            cin>>m;
            myPrioQueue.push(m);
        }
        int answer = 0;
        while(myPrioQueue.size()>1){
            int a = myPrioQueue.top();
            myPrioQueue.pop();
            int b = myPrioQueue.top();
            myPrioQueue.pop();
            answer += a+b;
            myPrioQueue.push(a+b);
        }
        cout<<answer<<endl;
    }
    return 0;
}

哈夫曼树的构造步骤：
（1）所有叶子节点放入集合中
（2）每次取出集合中的权值最小的两个叶子节点，作为新节点的左右节点，两元素权值之和作为新节点的权值，再把新节点放入集合中
（3）直到集合数为1
过程中所有取出的节点的权值之和即为最小带权路径长度和。
优先队列默认取出最大的元素，因此需要使用

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

来重新定义优先队列，这样每次取出的是最小的元素。