保研机试备考八:Huffman树

保研机试备考八:Huffman树,第1张

保研机试备考八: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 k1
如果 n − m ( k − 1 ) = 1 n-m(k-1)=1 nm(k1)=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;
}

优先队列: priority_queue//堆
哈希表:unordered_map


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/798587.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-06
下一篇 2022-05-06

发表评论

登录后才能评论

评论列表(0条)

保存