问题:

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;
}