哈夫曼树

哈夫曼树大概有两种考法，一种是合并果子的问题，就是最小或者最大的两两合并问题，另一种则是输出带权路径长度的问题，处理方式相仿，一般使用优先队列解决，优先队列的定义是：priority_queue<int,vector<int>,greater<int> > Q ;其中greater是指大顶堆，即堆顶的元素是最大的，相反小顶堆则是less，其他pop push top操作相同。

//带权路径长度
#include <iostream>
#include <queue>
using namespace std;
int main(){
    priority_queue<int, vector<int>, greater<int> >Q;
    int n, a;
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>a;
        Q.push(a);
    }
    int ans = 0;
    while (Q.size() > 1){
        int top1 = Q.top();
        Q.pop();
        int top2 = Q.top();
        Q.pop();
        ans += top1 + top2;
        Q.push(top1+top2);
    }
    cout<<ans<<endl;
}