哈夫曼树

1. 很经典的树
2. 适合压缩编码

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int N=1e4+10;
typedef long long LL;
int n;
priority_queue<LL,vector<LL>,greater<LL>>h;

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        LL x;
        scanf("%lld",&x);
        h.push(x);
    }
    LL res=0;
    while(!h.empty()){
        LL x=h.top();
        h.pop();
        if(h.empty()){
            printf("%lld",res);
            break;
        }
        else{
            LL y=h.top();
            h.pop();
            res+=x+y;
            h.push(x+y);
        }
    }
    return 0;
}