#include<iostream>
#include<vector>
using namespace std;

template<class T>
struct Less//仿函数
{
	bool operator()(const T& l, const T& r)
	{
		return l > r ? true : false;
	}
};
template<class T>
struct Greater//仿函数
{
	bool operator()(const T& l, const T& r)
	{
		return l < r ? true : false;
	}
};

template<class T,class functor>
class Heap
{
public:
	Heap(T* a, size_t n)
	{
		v.reserve(n);
		for (size_t i = 0; i < n; i++)
		{
			v.push_back(a[i]);
		}
		//构建堆
		for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		{
			AdJustDown(i,n);//向下调整
		}
	}
	void Push(const T& x)//插入
	{
		v.push_back(x);
		size_t n = v.size() - 1;
		AdJustUp(n);
	}
	void Pop()
	{
		size_t n = v.size() - 1;
		swap(v[0], v[n]);
		v.pop_back();
		AdJustDown(0, n - 1);
	}
	void Empty()
	{
		return v.empty();
	}
private:
	void AdJustDown(int i,size_t n)
	{
		functor G;
		int parent = i;
		int child = i * 2 + 1;
		while (child < n)
		{
			if (child<(n-1)&&G(v[child],v[child + 1]))
			{
				child++;
			}
			if (G(v[parent],v[child]))
			{
				swap(v[parent],v[child]);//交换
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}

		}
	}
	void AdJustUp(size_t i)//向上调整
	{
		functor G;
		int child = i;
		int parent = (i - 1) / 2;
		while (parent>=0)
		{
			if (G(v[child], v[parent]))
			{
				break;
			}
			else
			{
				swap(v[parent], v[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}
	}


private:
	vector<int> v;
};

首先了解一下vector这个头文件，vector：c++的一种数据结构，确切来说是一个类。他就相当于是一个动态数组，当程序员无法知道自己需要的数组大小时，可以用此方法来解决问题，节约空间。

vector中常用的函数有：

1.push_back   在数组的最后添加一个数据
2.pop_back    去掉数组的最后一个数据 
3.at                得到编号位置的数据
4.begin           得到数组头的指针
5.end             得到数组的最后一个单元+1的指针
6.front        得到数组头的引用
7.back            得到数组的最后一个单元的引用
8.max_size     得到vector最大可以是多大
9.capacity       当前vector分配的大小
10.size           当前使用数据的大小
11.resize         改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve      改变当前vecotr所分配空间的大小
13.erase         删除指针指向的数据项
14.clear          清空当前的vector
15.empty        判断vector是否为空

16.swap         与另一个vector交换数据

现在我们来看堆：

堆是一个静态二叉树，存放在顺序表中。

大堆：每个父节点都大于子节点

小堆：每个父节点都小于子节点

例如：a[]={ 12,11,13,12,16,18,15,17,14,19 };