哈夫曼树

概念：哈夫曼树通过反复合并权值最小的两棵树，最小化带权路径长度。把左、右边编码为 0、1，即得到无前缀歧义的哈夫曼编码。

关键步骤

将所有叶子权值放入小根堆；每次取出两项相加，累计合并代价，并将新权值压回。堆中剩一个元素时完成构造。

priority_queue<long long,vector<long long>,greater<long long>> pq;
long long ans=0;
while(pq.size()>1){
    long long a=pq.top(); pq.pop();
    long long b=pq.top(); pq.pop();
    ans+=a+b; pq.push(a+b);
}

复杂度

有 n 个初始权值时进行 n-1 次合并，时间 O(n log n)，堆空间 O(n)。权值和及总代价应使用 long long。