HEAP1 - Một chút về Huffman Tree
Tác giả: hieult
Ngôn ngữ: C++
#include<iostream>
#include<vector>
//#include<conio.h>
using namespace std;
vector<long long> a;
long n;
long long kq,tong;
int xuli()
{
long i,j,x,y;
make_heap(a.begin(),a.end());
kq = 0;
for (i=1;i<=n-1;i++)
{
x = a[0];
pop_heap(a.begin(),a.end());
a.pop_back();
y = a[0];
pop_heap(a.begin(),a.end());
a.pop_back();
kq = kq + x+y;
a.push_back(x+y);
push_heap(a.begin(),a.end());
}
}
int main()
{
long x,test,i,j;
cin>>test;
for (i=1;i<=test;i++)
{
cin>>n;
for (j=1;j<=n;j++)
{
cin>>x;
x = -x;
a.push_back(x);
}
xuli();
a.pop_back();
cout<<-kq<<endl;
}
//getch();
}