哈夫曼编码&哈夫曼树

[toc]

前置芝士

WPL

$所有叶子节点的权值*路径长度（深度）$

$WPL = \sum_{i=1}^nl_iw_i$。

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

graph

它的$WPL=9*3+(16+17)4+52+3+1$

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

哈夫曼树

1.定义

$WPL$最小的二叉树

上面的$T$即为一颗哈夫曼树

2.构造原则

权值越大越靠近根节点

3.构造过程

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

演示：

第一步

graph (1)

第二步 graph (2)

第三步

graph (3)

第四步

4.代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


    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叉哈夫曼树，并输出它的$WPL$,以及它的高度$h$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


#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