//数组实现 #include <iostream> #include <cstring> using namespace std; const int maxnode = 20000; int size; int heap[maxnode]; //这里是小根堆 //建堆 void Createheap() { memset(heap,0,sizeof(heap)); size = 0; return ; } void swap(int &a,int &b) { int tmp; tmp = a; a = b; b = tmp; return ; } //堆的插入 void up(int pos) { for(int i = pos; i > 0; i = (i-1)/2 ) { //调整新加的顶点的位置 if(heap[i] > heap[(i-1)/2]) //如果比根大,则break,这里是小根堆 break; else swap(heap[i],heap[(i-1)/2]); //否则,与根交换位置 } } void push(int x) { heap[size] = x; //在最右边插入节点 up(size); //调整 size++; //节点数++ } //堆的删除 void down(int pos) { int i,j; for( i = pos; i*2+1 < size;) { //注意是从根是0开始的,不是1啊啊啊啊啊啊 //根是i,那么左儿子是2*i+1 右儿子是2*i+2 j = i*2+1; //被删除节点的左儿子 if(j+1 < size && heap[j+1] < heap[j]) //找到左右儿子中较大的 j++; //右儿子 if(heap[i] < heap[j]) //若被删的节点比小儿子还小,那么符合小根堆 break; else swap(heap[i],heap[j]); //否则,交换 i = j; //heap[i],heap[j]交换后,被删除节点的位置要调整 } } void pop(int x) { size --; //是从0开始的 //最后一个节点给heap[0],经过调整会放在适当位置 //因为heap[size]赋给heap[0]后,在if(heap[i] < heap[j])时,肯定不成立的 heap[x] = heap[size]; down(x); } int main() { int a; int i = 0; Createheap(); while(cin >> a) { push(a); i++; } while(i--) { pop(0); cout << heap[0]<<endl; } return 0; }