题目描述
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入描述:
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出描述:
输出权值。
示例1
输入
5
1 2 2 5 9
输出
37
分析&代码
哈夫曼树（最优树）的原理是很容易理解的，在所有的节点集合中，不断的找出值最小的两个节点，然后以这两个节点的值的和新建一个节点，然后加入到集合中，重复这个过程，直到集合中只剩下一个节点的时候，一棵哈夫曼树就算建好了，所以在这个过程中，哈夫曼树不是唯一的，但是所有节点的值与权值的乘积的和是一定的。借助 优先队列 这种数据结构可以很轻松的创建哈夫曼树。在C++的标准库中也有优先队列这一数据结构可以直接调用：
需要引入的头文件（在队列的头文件中）：
#include<queue>创建优先队列：
priority_queue<int> Q;这样就创建了一个优先队列，但是仅仅是这样的话是创建的大顶堆，即队列首的元素是最大的元素，它的操作是跟queue一致的例如 Q.pop()，只是取开头元素改成了Q.top(),Q.push() 是向队列中插入一个元素。但是在创建哈夫曼树的过程中，我们要使用的是小顶堆，所以要指定基准优先级：
priority_queue<int,vector<int>, greater<int> > Q; //建立的小顶堆完整：
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<iostream>
using namespace std;
priority_queue<int, vector<int>, greater<int> > huffman;
int n;
int temp;
int main(){
while(cin>>n){
for(int i=0 ;i<n; i++){
cin>>temp;
huffman.push(temp);
}
int ans = 0;
while(huffman.size() > 1){ //结束条件是队列只剩下一个元素
int a = huffman.top();
huffman.pop();
int b = huffman.top();
huffman.pop();
ans += a + b;
huffman.push(a + b); //去除两个最小的元素，合并之后添加到队列中
}
cout<<ans<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116816.html
