保研机试备考八：Huffman树_C

保研机试备考八：Huffman树 AcWing 148. 合并果子题目

https://www.acwing.com/problem/content/150/

思路

霍夫曼树的本质是贪心，每次选最小的两个合并就行。
用优先队列维护一个小顶堆，每次从堆顶取两个元素合并即可，循环结束条件是堆的元素个数等于1了。

优先队列：priority_queue
默认是大顶堆
使之表示小顶堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名

代码

#include
#include
using namespace std;
int main()
{
    int n,a;
    priority_queue<int,vector<int>,greater<int>> m;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        m.push(a);
    }
    int sum=0;
    while(m.size()>1)
    {
        int x=m.top();
        m.pop();
        int y=m.top();
        m.pop();
        sum+=x+y;
        m.push(x+y);
    }
    cout<<sum;
    return 0;
}

AcWing 149. 荷马史诗题目

https://www.acwing.com/problem/content/151/

思路

将 k k k堆合并为一堆，最后实际上减少了 k − 1 k-1 k−1堆
如果 n − m ( k − 1 ) = 1 n-m(k-1)=1 n−m(k−1)=1,说明 n n n堆正好可以经过 m m m次合并，最后合并为一堆，如果不行，我们可以往里面插入空节点，直到它可以整除为止：
（因为实际没法每次都合并 k k k堆，那么我们尽量将下面合并的节点不合并 k k k堆，这样可以使总权值最小，为了统一 *** 作，可以用空节点代替）

while((n-1)%(k-1)) m.push({0,0}),n++;

然后每次合并的时候，要找到 k k k个节点中深度最小的节点，合并成的节点的深度接在它上面，这样可以使得“最长字符串的长度最短”。这里从下往上合并，深度最小，也即高度最大，要用max。

为什么res就是经过重新编码以后的最短长度？
因为res中有很多节点的权值是重复算的，重复算多少次，其实也就是根节点到该节点的路径长度，也即编码长度，所有的点都是这样，那其实加起来就是经过重新编码以后的最短总长度。

代码

#include
#include
#include
using namespace std;
typedef long long LL;  //1≤wi≤10的12次方，会爆int
typedef pair<LL,int> PLI;  //单词的出现次数（权值），在霍夫曼树中的高度
#define x first 
#define y second
int main()
{         //优先队列维护的小顶堆，每次只从堆顶取出最小元素
    priority_queue<PLI,vector<PLI>,greater<PLI>> m; 
    int n,k;
    LL w;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>w;
        m.push({w,0});   //初始每个点的深度为0
    }
    while((n-1)%(k-1)) m.push({0,0}),n++;
    LL res=0;
    while(m.size()>1)  //只要没合并为一个节点，就一直继续
    {
        int depth=0;
        LL sum=0;
        for(int i=0;i<k;i++)
        {
            auto p=m.top();
            m.pop();
            sum+=p.x;
            depth=max(depth,p.y);//记录一个最“浅”的深度
        }
        res+=sum;
        m.push({sum,depth+1});
    }
    cout<<res<<endl<<m.top().y;
    return 0;
}