2.Huffman树-哈夫曼树
实现思路：构建一颗哈夫曼树，求最短带权路径长度（树中所有的叶结点的权值乘上其到根结点的路径长度）
- 每次选择重量最小的两堆进行合并
- 使用小根堆存储每一堆果子，每次两次弹出堆顶元素，合并后就放入小根堆中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
int n;
cin>>n;
priority_queue<int ,vector<int>,greater<int>> heap;
while(n--){
int x;
cin>>x;
heap.push(x);
}
int res=0;
while(heap.size()>1){
int a=heap.top(),heap.pop();
int b=heap.top(),heap.pop();
res+=a+b;
heap.push(a+b);
}
cout<<res<<endl;
return 0;
}
|