最小堆和最优队列的C--STL实现.doc

最小堆：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool cmp(int a,int b)
{
return a>b;
}

int main()
{
int n,i;
vector<int> v;
int num;
int a;
__int64 sum;
while(scanf("%d",&n)!=EOF)
{
sum=0;
while(n--)
{
scanf("%d",&num);
v.push_back(num);
}
make_heap(v.begin(),v.end(),cmp);
while(v.size()!=1)
{
a=v.front();
pop_heap(v.begin(),v.end(),cmp);
v.pop_back();
//make_heap(v.begin(),v.end(),cmp);
a+=v.front();
pop_heap(v.begin(),v.end(),cmp);
v.pop_back();
//make_heap(v.begin(),v.end(),cmp);
v.push_back(a);
push_heap(v.begin(),v.end(),cmp);
sum+=a;
}
printf("%I64d\n",sum);
v.pop_back();
}
return 0;
}
最优队列：
#include<iostream>
#include<queue>
//#include<vector>
#include<algorithm>
using namespace std;

int main(){
int num,n,i,a;
priority_queue<int> plank;
/*vector <int> v;
//make_heap(v.begin(),v.end(),cmp);//通过更改cmp 到return a>b 就变成了最小堆
//v.front();
//pop_heap(v)
v.pop_back();*/
//__int64 mo;
__int64 mo;
while(scanf("%d",&n)!=EOF){
mo=0;
while(n--){
scanf("%d",&num);
plank.push(-num);
}
while(plank.size()!=1){
a=plank.top();
plank.pop();
a+=plank.top();
mo+=a;
plank.pop();
plank.push(a);
}
plank.pop();
//printf("%I64d\n",-mo);
printf("%I64d\n",-mo);
}

return 0;
}