哈夫曼编码&哈夫曼树

[toc]

前置芝士

WPL

。

e.g. 如图为一颗二叉树

它的

显然有一个性质: =所有非叶子节点权值的和

哈夫曼树

1.定义

最小的二叉树

上面的即为一颗哈夫曼树

2.构造原则

权值越大越靠近根节点

3.构造过程

贪心算法，用优先队列，每次取出权值最小和次小的两项，作为叶子节点构造一棵二叉树。

演示：

第一步

第二步

第三步

第四步

4.代码实现

cpp

    FOR(i,1,n){
        int tmp;
        cin>>tmp;
        q.push(make_tuple(tmp,1));
    }
    cnt=n;
    while(cnt>1){ 
        // cout<<"cnt="<<cnt<<endl;
        sum=h=0;
        FOR(i,1,2){
            auto [w,hh] = q.top();q.pop();
            sum+=w;
            h=max(hh,h);
        }
        h++;
        cnt--;
        ans+=sum;
        q.push(make_tuple(sum,h));
    }
    cout<<ans<<endl<<get<1>(q.top())-1<<endl;

5.练习题

P2168 NOI2015

题意

建造一颗k叉哈夫曼树，并输出它的,以及它的高度

代码

cpp

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
using namespace std;
int n,k,cnt,sum,ans,h;
typedef tuple<int,int> node;
priority_queue<node,vector<node> ,greater<node>> q;
signed main(){
    // freopen("1.in","r",stdin);
    cin>>n>>k;
    FOR(i,1,n){
        int tmp;
        cin>>tmp;
        q.push(make_tuple(tmp,1));
    }
    if((n-1)%(k-1))cnt=(k-1)-(n-1)%(k-1);
    FOR(i,1,cnt)q.push(make_tuple(0,1));
    cnt+=n;
    while(cnt>1){ 
        // cout<<"cnt="<<cnt<<endl;
        sum=h=0;
        FOR(i,1,k){
            auto [w,hh] = q.top();q.pop();
            sum+=w;
            h=max(hh,h);
        }
        h++;
        cnt-=(k-1);
        ans+=sum;
        q.push(make_tuple(sum,h));
    }
    cout<<ans<<endl<<get<1>(q.top())-1<<endl;
}

哈夫曼编码（初赛知识）

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

参考

BV1hK4y1k7Wr