第四十章贪心算法——Huffman树-创新互联
贪心算法——Huffman树
名称栏目:第四十章贪心算法——Huffman树-创新互联
标题URL:http://pwwzsj.com/article/dshpdo.html
- 一、问题
- 二、思路
- 1、哈夫曼树算法
- 2、算法实现
- 三、代码
这道题是一道经典的哈夫曼问题,解决的方案就是我们每次挑出两堆最小的果子合并。那么这个合并的过程可以画成一棵完全二叉树。如下图所示:
那么怎计算呢?其实就是把除了根节点以为的点所富有的权值加在一起即可。
如下图所示:
我们对上述的计算式子稍作变形,就会发现图中红色式子的规律。
那么为什么这个算法就能保证最小呢?
其实感性的理解一下也是可以知道的,越靠下的节点,被算的次数是越多的,因此我们让这些算的次数多的节点带有一个较小的权值,这样就能保证整体最小。
严格的证明方法的话,大家可以采用反证法。这里就不多介绍了。
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树-创新互联
标题URL:http://pwwzsj.com/article/dshpdo.html