求哈夫曼树根节点权值
#### C++ 代码
/*
因为果子可以随意两堆合并,所以可以用经典哈夫曼树模型,每次合并重量最小的两堆即可
*/
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N=10010;
int main()
{
int n,weight,first,second,sum=0;
scanf("%d",&n);
priority_queue<int ,vector<int>,greater<int>> heap;
for(int i=0;i<n;i++)
{
scanf("%d",&weight);
heap.push(weight);
}
if(n==1)
{
printf("0");//只有一堆无需搬运
}
else
{
while(heap.size()!=1)
{
first=heap.top();
heap.pop();
second=heap.top();
heap.pop();
sum+=first+second;
heap.push(first+second);
}
printf("%d",sum);
}
return 0;
}