【模板】哈夫曼树

posted on 2021-08-02 20:03:57 | under 学术 | source

网上对哈夫曼树的讲解太少了

清一色指针

整个 OIer 能看的吧

虽然还是很恶心

下面是哈夫曼树的模板，解决的是经典问题：压缩字符串

#include <queue>
#include <string>
#include <iostream>
using namespace std;
template<int N,class var,class ext,int extlimit> struct Huffman{
    struct node{
        var w;ext e;
        int i,l,r;
        node(var w=0,ext e=0,int i=0,int l=0,int r=0):
            w(w),e(e),i(i),l(l),r(r){}
        bool operator>(const node &b)const{return w>b.w;}
    } a[N+10];
    int cnt,root;
    string code,ans[extlimit+10];
    Huffman():cnt(0),code(""){}
    string operator[](ext e){return ans[e];}
    node newnode(var w,ext e,int l=0,int r=0){return cnt++,a[cnt]=node(w,e,cnt,l,r);}
    void build(int n,var a[],ext e[]){
        priority_queue<node,vector<node>,greater<node> > q;
        for(int i=1;i<=n;i++) q.push(newnode(a[i],e[i]));
        while(q.size()>1){
            node t1=q.top();q.pop();
            node t2=q.top();q.pop();
            q.push(newnode(t1.w+t2.w,0,t1.i,t2.i));
        }
        return getcode(root=q.top().i);
    }
    void getcode(int now){
        if(!now) return ;
        if(!a[now].l&&!a[now].r) return (void)(ans[a[now].e]=code);
        code+='0',getcode(a[now].l),code.erase(--code.end());
        code+='1',getcode(a[now].r),code.erase(--code.end());
    }
};
Huffman<100010,int,char,128> huffman;
int n;
char a[100010];
int t[128];
int ipt[128],cnt;
char ipt2[128];
int main(){
    cin>>n>>(a+1);
    for(int i=1;i<=n;i++) t[a[i]*1u]++;
    for(int i=1;i<=127;i++){
        if(t[i]) ipt[++cnt]=t[i],ipt2[cnt]=i;
    }
    huffman.build(cnt,ipt,ipt2);
    for(int i=1;i<=n;i++) cout<<huffman[a[i]];
    return 0;
}

鉴于某些出题人（指 P2168 的）会让我们构造 \(k\) 叉哈夫曼树，那多挂一个代码吧：

#include <map>
#include <queue>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
ostream& operator<<(ostream &fout,vector<int> &v){
    for(size_t i=0;i<v.size();i++) fout<<v[i]<<" ";
    return fout;
}
int K=2;
template<class var,class ext> struct Huffman{
    typedef vector<int> vec;
    struct node{
        var w;ext e;int i,h;vec ch;
        node(var w=0,ext e=0,int i=-1,int h=0,vec ch=vec()):
            w(w),e(e),i(i),h(h),ch(ch){}
        bool operator>(const node &b)const{
            if(w==b.w) return h>b.h;
            return w>b.w;
        }
    };
    vector<node> a;
    map<ext,string> ans;
    priority_queue<node,vector<node>,greater<node> > q;
    string operator[](ext e){return ans[e];}
    void insert(var w,ext e){q.push(newnode(w,e));}
    node newnode(var w,ext e,int h=0,vec ch=vec()){
        node tmp=node(w,e,a.size(),h,ch);
        return a.push_back(tmp),tmp;
   	}
    void build(){
        while((int)q.size()>=K){
            vec ch;var tot=0;
            int maxh=0;
            for(int i=0;i<K;i++){
                node tmp=q.top();q.pop();
                tot+=tmp.w;
                ch.push_back(tmp.i);
                maxh=max(maxh,tmp.h);
            }
            q.push(newnode(tot,0,maxh+1,ch));
        }
        return getcode(q.top().i,"");
    }
    void getcode(int now,string code){
        if(!a[now].ch.size()) return (void)(ans[a[now].e]=code);
        for(int i=0;i<K;i++) getcode(a[now].ch[i],code+(char)('0'+i));
    }
};
Huffman<LL,int> a;
int n;
LL w[100010];
LL ans,maxn;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        a.insert(w[i],i);
    }
    if((n-1)%(K-1)!=0){
        for(int i=1;i<=K-1-(n-1)%(K-1);i++) a.insert(0,114514);
    }
    a.build();
    for(int i=1;i<=n;i++){
        ans+=a[i].size()*w[i];
        maxn=max(maxn,(LL)a[i].size());
    }
    cout<<ans<<endl<<maxn<<endl;
    return 0;
}