洛谷在线测试P3378_模板堆

/*  Name: P3378_模板堆  Copyright:   Author:   Date: 01-03-17 07:35  Description:   P3378 【模板】堆如题，初始小根堆为空，我们需要支持以下3种操作：操作1： 1 x 表示将x插入到堆中操作2： 2 输出该小根堆内的最小数操作3： 3 删除该小根堆内的最小数输入输出格式输入格式：第一行包含一个整数N，表示操作的个数接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：操作1： 1 x操作2： 2操作3： 3输出格式：包含若干行正整数，每行依次对应一个操作2的结果。输入输出样例输入样例#1：51 21 5232输出样例#1：25说明时空限制：1000ms,128M数据规模：对于30%的数据：N<=15对于70%的数据：N<=10000对于100%的数据：N<=1000000（注意是6个0。。。不过不要害怕，经过编者实测，堆是可以AC的）*/#include<iostream>using namespace std;template <typename type> class MinHeap{	public:		   MinHeap(int maxSize); //创建一个容量为maxSize的空堆			   ~MinHeap() {delete []heap;} //析构函数		   		   const type & top() {return heap[0];} //返回堆顶的最小元素 		   bool push(const type &x); //将x插入到最小堆		   bool pop(); //删除堆顶的最小元素		      	PRivate:			type *heap;   //存放堆的元素的数组 			int capacity; //堆的容量 			int size;     //堆的长度，即当前元素个数 						void FilterDown(int i); //从下标i到m自顶向下进行调整成为最小堆			void FilterUp(int i); //从下标i到0自底向上进行调整成为最小堆	};template <typename type> MinHeap<type>::MinHeap(int maxSize){    capacity = maxSize;    heap = new type[capacity];    size = 0;}template <typename type> void MinHeap<type>::FilterDown(int i) //从下标i到堆的尾部自顶向下进行调整成为最小堆{    type t = heap[i];   //保存heap[i]的值以备放到适合的位置     int child = i * 2 + 1; //指向左孩子           while (child < size) //有左孩子     { 	    if (child+1 < size && heap[child+1] < heap[child]) //有右孩子，且右孩子更小些，定位其右孩子               child++;                    if (heap[child] < t)//用较小值覆盖其父亲结点的值，即将空位下滤到新的位置         {        	    heap[i] = heap[child];        		    i = child;   		    child = i * 2 + 1;        }          else              break;  	}        heap[i] = t;}template <typename type> void MinHeap<type>::FilterUp(int i) //从下标i到0自底向上进行调整成为最小堆{    type t = heap[i];    int f = (i - 1) >> 1;        while (i > 0 && t < heap[f]) //若比父亲结点小，则用父亲结点的值覆盖该结点，即将空位上滤到新的位置     {        heap[i] = heap[f];	           i = f;        f = (i - 1) >> 1;	}        heap[i] = t;}template <typename type> bool MinHeap<type>::push(const type &x) //将x插入到最小堆{    //从尾部插入并向上调整成最小堆，然后长度增1     heap[size++] = x;    FilterUp(size-1);     return true;}template <typename type> bool MinHeap<type>::pop() //删除堆顶的最小元素{    heap[0] = heap[--size];//用尾部元素覆盖顶部元素，然后长度减1    FilterDown(0); //顶部元素向下调整成最小堆    return true;}int main(){	MinHeap<int> obj(400000);	int n, com, x;		cin >> n;	for (int i=0; i<n; i++)	{	 	cin >> com;	 	if (com == 1)	 	{ 		    cin >> x; 		    obj.push(x);   		} 		else if (com == 2)	 	{ 		    cout << obj.top() << endl; 		} 		else 		{		 	obj.pop();  		}	}	//    system("pause");				   	return 0;}