学步园

堆是一种简单高效的数据结构，在很多常用算法的优化上大显身手。

堆的常数很小，同样的数据，用堆来排序和快排的速度几乎相等，但是平衡树的速度会慢很多，Splay慢了两倍多。。

简单的学习一下堆，把模板发出来与大家分享

CODE（小根堆，排序）：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 200010
#define INF 0x7f7f7f7f
using namespace std;

struct SmallHeap{
	int num[MAX];
	int last;
	int Top() {
		return num[1];
	}
	void Insert(int x) {
		num[++last] = x;
		int now = last;
		while(num[now] < num[now >> 1] && now > 1)
			swap(num[now],num[now >> 1]),now >>= 1;
	}
	void Pop() {
		num[1] = num[last--];
		int now = 2;
		while(now <= last) {
			if(num[now] > num[now + 1])	++now;
			if(num[now] < num[now >> 1])	swap(num[now],num[now >> 1]),now <<= 1;
			else	break;
		}
	}
}heap;

int cnt;

int main()
{
	cin >> cnt;
	for(int x,i = 1;i <= cnt; ++i) {
		scanf("%d",&x);
		heap.Insert(x);
	}
	for(int i = 1;i <= cnt; ++i) {
		printf("%d\n",heap.Top());
		heap.Pop();
	}
	return 0;
}