first-blog

数据结构复习篇1——哈夫曼树

定义

1. 结点的带权路径：从根结点到该结点之间的路径长度与该结点的权的乘积

2. 树的带权路径：所有叶子结点的带权路径长度之和

   举例：

   

3. 哈夫曼树：将n个权值作为二叉树的n个叶子结点，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树

构造哈夫曼树

给我们n个结点，如何构造出一颗哈夫曼树呢？

在这里，我们可以尝试使用贪心的策略，如果要是的WPL最小，那权值大的点应该放在深度很小的地方，权值小的点应该放到底层，即深度很大的地方。所以每次构造时选择两个权值最小的结点进行构造。

举例：给定4，7，9，10这四个结点，如何构造一个是的WPL最小的二叉树呢？

·Step1: 从这个结点集合中选择权值最小的两个点，组成一个新结点。

在这个例子里面，选择 4 和 7 ，构造成新的点11

·Step2: 把选过的结点从结点集合排出，新结点11加入结点集合，重复step1，直至结点集合里面只有一个结点为止。

根据上述步骤，最后组成的哈夫曼树如图所示。

代码实践

对于上述的方法，很容易想到如果要构造一个哈夫曼树可以使用最小堆（priority_queue）实现。每次从堆中弹出的两个结点即是我们要取的构造新结点的组成结点。

这里，我们将二叉树扩展到K叉树，即每个父结点由K个字节的组成。

荷马史诗

引入问题：（该问题来自acwing149. 荷马史诗 - AcWing题库)

一部《荷马史诗》中有 n 种不同的单词，从 1到 n 进行编号。其中第 i𝑖 种单词出现的总次数为 𝑤𝑖。

达达想要用 𝑘 进制串 𝑠𝑖 来替换第 𝑖 种单词，使得其满足如下要求:

对于任意的 1≤i,j≤n，i≠j1≤𝑖,𝑗≤𝑛，𝑖≠𝑗，都有：𝑠𝑖 不是 𝑠𝑗 的前缀。

现在达达想要知道，如何选择 𝑠𝑖，才能使替换以后得到的新的《荷马史诗》长度最小。

在确保总长度最小的情况下，达达还想知道最长的 𝑠𝑖 的最短长度是多少？

一个字符串被称为 k𝑘 进制字符串，当且仅当它的每个字符是 0 到 𝑘−1 之间（包括 0 和 𝑘−1）的整数。

字符串 𝑆𝑡𝑟1 被称为字符串 𝑆𝑡𝑟2 的前缀，当且仅当：存在 1≤t≤m1≤𝑡≤𝑚，使得 𝑆𝑡𝑟1=𝑆𝑡𝑟2[1..𝑡]。

其中，𝑚 是字符串𝑆𝑡𝑟2 的长度，𝑆𝑡𝑟2[1..𝑡] 表示𝑆𝑡𝑟2 的前 𝑡 个字符组成的字符串。

注意: 请使用 64 位整数进行输入输出、储存和计算。

输出文件包括 2 行。

第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。

第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串 𝑠𝑖 的最短长度。

对于该问题，很明显可以看出需要我们构造一个k叉树使其$WPL$达到最小，另外，对于权值相同的结点，要优先考虑深度小的来构造，避免树的深度过大。

下面是代码实现。

# include <iostream>
# include <queue>
# include <vector>

using namespace std;

typedef long long  LL;
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> h;

int n,k;


int main(){
    cin>>n>>k;
    LL a;
    for(int i=0; i<n; i++){
        cin>>a;
        h.push({a,0});
    }
    //对于填不满k叉树的结点，补0来处理
    while((n-1)%(k-1)){
        h.push({0,0});
        n++;
    }
    
    LL res = 0;
    
    while(h.size()>1){
        
        int depth = 0;
        LL s = 0;
        for(int i=0; i<k; i++){
            auto p = h.top();
            s += p.first;
            depth = max(depth, p.second);
            h.pop();
        }
        res += s;
        h.push({s, depth+1});
        
        
    }
    cout<<res<<endl;
    cout<<h.top().second<<endl;
    
    
    
}