哈夫曼树

哈夫曼树，又称最优树，是一类带权路径长度最短的树。
带权路径：即各点与根的距离*点的权值之和

构造方式

1. 对于2叉哈夫曼树，使用贪心策略，每次选出最小的两个节点，合并成一个大节点
2. 对于K叉哈夫曼树，每次应该选出K个节点合并成一个大节点，但当总的节点个数无法满足每一个父亲均有K个儿子时，需要添加一些权值为0的节点，使得节点数(n-1)%(k-1)==0，让节点少在最底层，证明见进阶指南P84-85

例题

荷马史诗

题面

思路

即构建一个哈夫曼树，注意补0,同时，因为要深度最小，所以在权值最小的基础上，增加深度更小的优先合并

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k,ansh;
ll w[100005],ans;
struct node{
    ll v;
    int h;
};

bool operator <(node x,node y){
    return x.v>y.v||x.v==y.v&&x.h>y.h;
}

priority_queue <node> q;

int main(){
    cin>>n>>k;
    for (int i=1;i<=n;++i) scanf("%lld",&w[i]);
    for (int i=1;i<=n;++i){
        q.push({w[i],0});
    }
    while ((n-1)%(k-1)!=0){
        n++;
        q.push({0,0});
    }
    while (q.size()>=k){
        node t{0,0};
        for (int i=1;i<=k;++i){
            node tmp=q.top();
            q.pop();
            t.v+=tmp.v;
            t.h=max(t.h,tmp.h+1);
        }
        q.push(t);
        ans+=t.v;
        ansh=max(ansh,t.h);
    }
    printf("%lld\n%d",ans,ansh);
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/83/