第四十章贪心算法——Huffman树-创新互联

贪心算法——Huffman树
  • 一、问题
  • 二、思路
    • 1、哈夫曼树算法
    • 2、算法实现
  • 三、代码

成都创新互联公司专业为企业提供炎陵网站建设、炎陵做网站、炎陵网站设计、炎陵网站制作等企业网站建设、网页设计与制作、炎陵企业网站模板建站服务，十多年炎陵做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。一、问题

在这里插入图片描述

二、思路 1、哈夫曼树算法

这道题是一道经典的哈夫曼问题，解决的方案就是我们每次挑出两堆最小的果子合并。那么这个合并的过程可以画成一棵完全二叉树。如下图所示：
在这里插入图片描述
那么怎计算呢？其实就是把除了根节点以为的点所富有的权值加在一起即可。
如下图所示：
在这里插入图片描述
我们对上述的计算式子稍作变形，就会发现图中红色式子的规律。

那么为什么这个算法就能保证最小呢？

其实感性的理解一下也是可以知道的，越靠下的节点，被算的次数是越多的，因此我们让这些算的次数多的节点带有一个较小的权值，这样就能保证整体最小。

严格的证明方法的话，大家可以采用反证法。这里就不多介绍了。

2、算法实现

我们每次都是选出两个最小的，对于这种从一堆数字中选出前几个最小的值，这种情形下，我们可以采用小根堆。

三、代码
#include#includeusing namespace std;
int main()
{priority_queue,greater>q;
    int n,ans=0;
    cin>>n;
    for(int i=0;iint x;
        scanf("%d",&x);
        q.push(x);
    }
    while(q.size()>1)
    {int top1=q.top();
        q.pop();
        int top2=q.top();
        q.pop();
        ans+=top1+top2;
        q.push(top1+top2);
    }
    cout<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享标题：第四十章贪心算法——Huffman树-创新互联
转载注明：https://www.cdcxhl.com/article10/dshpdo.html

成都网站建设公司_创新互联，为您提供做网站、网站维护、网站营销、面包屑导航、建站公司、自适应网站

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

成都网页设计公司

虚拟主机知识

同城分类信息