哈夫曼树

哈夫曼树

哈夫曼树是带权路径长度WPL(Weighted Path Length)最小的二叉树,也是最优二叉树。

哈夫曼树的构造,选出最小的和次小的节点合并权值形成新的节点,再重复。

有一个重要结论:最小带权路径长度为非叶子结点的和

##求解最小带权路径长度
为了方便的得到两个最小的节点,使用优先队列来实现,可以在O(logn)的时间内,取出n个元素中的最小元素。

1
2
3
4
5
6
7
8
9
priority_queue<int , vector<int> , greater<int> >Q

//或者自定义排序
struct cmp{ //整形最小优先队列
bool operator()(const int &a,const int&b){
return a>b;
}
};
priority_queue<int,vector<int>,cmp> Q;

这样构建一个递增的优先队列。队列最上面是最小的元素。
根据上面的结论只需要对非叶子节点相加即可
哈夫曼树

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
26
27
28
#include <iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int , vector<int>,greater<int> > Q;
int n;
while(cin>>n){
for(int i=0;i<n;i++){
int temp;
cin>>temp;
Q.push(temp);
}
int sum = 0;
while(Q.size()>1){
int a = Q.top();
Q.pop();
int b = Q.top();
Q.pop();
sum+=(a+b);
Q.push(a+b);
}
while(!Q.empty())
Q.pop();
cout<<sum<<endl;
}
return 0;
}