/*  Name: P3378_模板堆  Copyright:   Author:   Date: 01-03-17 07:35  Description:   P3378 【模板】堆如題，初始小根堆為空，我們需要支持以下3種操作：操作1： 1 x 表示將x插入到堆中操作2： 2 輸出該小根堆內(nèi)的最小數(shù)操作3： 3 刪除該小根堆內(nèi)的最小數(shù)輸入輸出格式輸入格式：第一行包含一個(gè)整數(shù)N，表示操作的個(gè)數(shù)接下來(lái)N行，每行包含1個(gè)或2個(gè)正整數(shù)，表示三種操作，格式如下：操作1： 1 x操作2： 2操作3： 3輸出格式：包含若干行正整數(shù)，每行依次對(duì)應(yīng)一個(gè)操作2的結(jié)果。輸入輸出樣例輸入樣例#1：51 21 5232輸出樣例#1：25說(shuō)明時(shí)空限制：1000ms,128M數(shù)據(jù)規(guī)模：對(duì)于30%的數(shù)據(jù)：N<=15對(duì)于70%的數(shù)據(jù)：N<=10000對(duì)于100%的數(shù)據(jù)：N<=1000000（注意是6個(gè)0。。。不過(guò)不要害怕，經(jīng)過(guò)編者實(shí)測(cè)，堆是可以AC的）*/#include<iostream>using namespace std;template <typename type> class MinHeap{	public:		   MinHeap(int maxSize); //創(chuàng)建一個(gè)容量為maxSize的空堆			   ~MinHeap() {delete []heap;} //析構(gòu)函數(shù)		   		   const type & top() {return heap[0];} //返回堆頂?shù)淖钚≡?		   bool push(const type &x); //將x插入到最小堆		   bool pop(); //刪除堆頂?shù)淖钚≡?	      	PRivate:			type *heap;   //存放堆的元素的數(shù)組 			int capacity; //堆的容量 			int size;     //堆的長(zhǎng)度，即當(dāng)前元素個(gè)數(shù) 						void FilterDown(int i); //從下標(biāo)i到m自頂向下進(jìn)行調(diào)整成為最小堆			void FilterUp(int i); //從下標(biāo)i到0自底向上進(jìn)行調(diào)整成為最小堆	};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) //從下標(biāo)i到堆的尾部自頂向下進(jìn)行調(diào)整成為最小堆{    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)//用較小值覆蓋其父親結(jié)點(diǎn)的值，即將空位下濾到新的位置         {        	    heap[i] = heap[child];        		    i = child;   		    child = i * 2 + 1;        }          else              break;  	}        heap[i] = t;}template <typename type> void MinHeap<type>::FilterUp(int i) //從下標(biāo)i到0自底向上進(jìn)行調(diào)整成為最小堆{    type t = heap[i];    int f = (i - 1) >> 1;        while (i > 0 && t < heap[f]) //若比父親結(jié)點(diǎn)小，則用父親結(jié)點(diǎn)的值覆蓋該結(jié)點(diǎn)，即將空位上濾到新的位置     {        heap[i] = heap[f];	           i = f;        f = (i - 1) >> 1;	}        heap[i] = t;}template <typename type> bool MinHeap<type>::push(const type &x) //將x插入到最小堆{    //從尾部插入并向上調(diào)整成最小堆，然后長(zhǎng)度增1     heap[size++] = x;    FilterUp(size-1);     return true;}template <typename type> bool MinHeap<type>::pop() //刪除堆頂?shù)淖钚≡貃    heap[0] = heap[--size];//用尾部元素覆蓋頂部元素，然后長(zhǎng)度減1    FilterDown(0); //頂部元素向下調(diào)整成最小堆    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;}