数据结构第6讲 Huffman编码和Huffman树

第6讲 Huffman编码和Huffman树

1.Huffman编码和Huffman树

(1) Huffman编码
a. 前缀编码: 是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。

b. 树的带权路径长度(WPL)

c. 构造过程

1.所有点的度数必不为1

2.一定存在一个最优解，权最小的2个点互为兄弟

最优解 36<58

每次取最小的2个合并

(2) Huffman树

AcWing 148. 合并果子

c++:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int n;
    cin>>n;
    
    priority_queue<int , vector<int>,greater<int> > heap ;// 小根堆
    
    while (n -- ){
        int x;
        cin>>x;
        heap.push(x);
    }
    
    int res = 0;
    
    while(heap.size()>1){ 
        int a =  heap.top();heap.pop(); //当前最小值
        int b =  heap.top();heap.pop(); // 当前次小值
        res += a+b;
        heap.push(a+b);
        
    }
    
    cout<<res<<endl;
    return 0;
}

扩展：之前是2进制编码，及二叉树

当为 K 进制编码 ， K叉树，类同二叉树

每次合并最小的 K 个数

每次减少k 个数，n >>> n-(k-1) 最后是否能 (n-1)/(k-1)??? （n点数 k分叉数）

这时候我们在前面补0使其能整除 0不提供代价补任意个都可

二叉树中因为 k-1 = 1不用考虑