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