最大堆
问题：
Max Heap
题目内容：
實作Max heap的三種操作：push, pop, top。
指令0 x：代表push，將x push進max heap。
指令1 : 代表pop，將最大的數字pop出來，若heap為空則忽略這道指令。
指令2 : 代表top，將最大的數字印出來，若heap為空則忽略這道指令。
输入格式:
本題只有一道測資。
測資第一行為一個數字N，代表接下來有N行指令。每行指令個格式如題目敘述。
所有push的數字皆不相同。
0 < N < 20000
0 < x < 10000000
输出格式：
將所有top指令輸出的數字作加總，最後輸出這個和。
Hint : 注意overflow!
输入样例：
15
1
0 9550684
0 8533293
1
2
2
1
0 505825
0 9809892
0 1484329
0 4958409
0 3788064
0 28006
2
0 2979864
输出样例：
26876478
时间限制：100ms内存限制：128000kb
利用数组：
#include <iostream>
#define N 200000
long long percUp(long long idx, long long array[])
{
long long temp,upper;
while(idx>=2)
{
upper = idx/2;
if(array[upper]>array[idx])
{
temp = array[idx];
array[idx] = array[upper];
array[upper] = temp;
}
idx = upper;
}
return 0;
}
int insert(long long array[], long long size, long long value)
{
array[size+1] = value;
percUp(size+1, array);
return 0;
}
long long minChildIdx(long long array[], long long father, long long size)
{
if(2*father+1>size)
{
return 2*father;
}
else
{
if(array[2*father]<array[2*father+1])return 2*father;
else return 2*father+1;
}
}
int percDown(long long array[], long long size, long long idx)
{
long long minidx, temp;
while(2*idx<=si***idx=minChildIdx(array,idx,size);
if(array[idx]>array[minidx])
{
temp=array[minidx];
array[minidx]=array[idx];
array[idx] = temp;
}
idx = minidx;
}
return 0;
}
long long delMin(long long array[], long long size)
{
if(size==0) return -1;
long long value = array[1];
array[1]=array[size];
size = size-1;
percDown(array,size,1);
return value;
}
int main()
{
long long array[N];
long long size=0,num,i,code,value,j;
array[0]=-189453;
long long count=0;
std::cin>>num;
size=0;
for(i=0;i<num;i++)
{
std::cin>>code;
if(code==0)
{
std::cin>>value;
insert(array,size,-value);
size++;
}
else
if(code==1)//pop
{
if(size==0)
{
continue;
}
else
{
delMin(array,size);
size--;
}
}
else
if(code==2)//top
{
if(size==0)
{
continue;
}
else
{
count+=-array[1];
//std::cout<<"plus:"<<-array[1]<<std::endl;
}
}
//std::cout<<"the current array is :"<<std::endl;
/*
for(j=1;j<=size;j++)
{
std::cout<<array[j]<<" ";
}
std::cout<<std::endl;
*/
}
std::cout<<count;
return 0;
}利用STL
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<long> que;
int n, op;
long x;
cin >> n;
long sum = 0;
for (int i=0; i<n; ++i) {
cin >> op;
if (op == 0) {
cin >> x;
que.push(x); // 插入元素
}
else if (op == 1) {
if (!que.empty()) {
que.pop(); // 弹出末端元素， 即最大元素
}
}
else if (op == 2) {
if (!que.empty()) {
sum += que.top(); // 将最大元素累加
}
}
}
cout << sum; // 输出结果
return 0;
}
