哈夫曼树求wpl:
设置一个小根堆存储结点,方便取出最小的两个结点。每次合并堆中最小的两个结点,加入wpl和堆,直到堆的大小为1。
#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 wpl = 0;
while(heap.size() > 1){
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
int c = a + b;
wpl += c;//累加wpl
heap.push(c);
}
cout<<wpl<<endl;
return 0;
}