文章
4
粉丝
168
获赞
3
访问
22.4k
//哈夫曼树的带权路径长度
//总结
//法一:①先对权值从小到大排序。
//②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点的左右子结点。
//③两个老的结点去掉,新的结点放入再次排序然后重复过程②。
//④直到完全生成一棵树。
//⑤计算的时候,只计算那些初始权值里面有的值,把它乘以深度
//(和传统说的深度不一样,是传统说的深度减一)加起来就是路径长度。
//法二:哈夫曼树也可以通过小根堆实现。小根堆每次弹出两个值,然后将二者的和再插入小根堆中。
#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
priority_queue<int, vector<int>, greater<int>> pq;//定义小根堆pq
int num;
for (int i = 0; i < n; i++)
{
cin >> num;
pq.push(num);
}
int sum = 0;
...
登录后发布评论
大家好,新人霸道哦大家好,新人霸道哦
大家好,新人霸道哦大家好,新人霸道哦大家好,新人霸道哦大家好,新人霸道哦