手写大根堆与小根堆

#include <algorithm>
#include <queue>

using namespace std;

template <typename T>
class heap {
	
private:
	vector<T> a;
	int pa, son;
	
public:
	inline void init()
	{
		a.push_back(0);
	}
	inline void pop()
	{
		a[1] = a.back(), pa = 1, son = 2;
		a.pop_back();
		while (son < a.size())
		{
			if (a[son] < a[pa] && a[son + 1] >= a[son]) swap(a[son], a[pa]);
			else if (a[++ son] < a[pa]) swap(a[son], a[pa]);
			else break;
			pa = son, son <<= 1;
		}
		if (a[son] < a[pa]) swap(a[son], a[pa]);
	}
	inline void push(T x)
	{
		a.push_back(x);
		son = a.size() - 1, pa = son >> 1;
		while (pa >= 1)
		{
			if (a[pa] > a[son]) swap(a[pa], a[son]);
			else break;
			son = pa, pa >>= 1;
		}
	}
	inline T top()
	{
		return a[1];
	}
	inline int size()
	{
		return a.size() - 1;
	}
	inline bool empty()
	{
		return !(a.size() - 1);
	}
	inline void make(int *begin, int *end)
	{
		for (int *it = begin; it <= end; it ++)
		a.push_back(*it);
		make_heap(a.begin() + 1, a.end(), greater<int>());
	}
	inline void operator = (const heap h)
	{
		a.clear();
		for (int i = 0; i < h.a.size(); i ++)
		a.push_back(h.a[i]);
	}
};

template <typename T>
class less_heap {
	
private:
	vector<T> a;
	int pa, son;
	
public:
	inline void init()
	{
		a.push_back(0);
	}
	inline void pop()
	{
		a[1] = a.back(), pa = 1, son = 2;
		a.pop_back();
		while (son < a.size())
		{
			if (a[son] > a[pa] && a[son + 1] <= a[son]) swap(a[son], a[pa]);
			else if (a[++ son] > a[pa]) swap(a[son], a[pa]);
			else break;
			pa = son, son <<= 1;
		}
		if (a[son] > a[pa]) swap(a[son], a[pa]);
	}
	inline void push(T x)
	{
		a.push_back(x);
		son = a.size() - 1, pa = son >> 1;
		while (pa >= 1)
		{
			if (a[pa] < a[son]) swap(a[pa], a[son]);
			else break;
			son = pa, pa >>= 1;
		}
	}
	inline T top()
	{
		return a[1];
	}
	inline int size()
	{
		return a.size() - 1;
	}
	inline bool empty()
	{
		return !(a.size() - 1);
	}
	inline void make(int *begin, int *end)
	{
		for (int *it = begin; it <= end; it ++)
		a.push_back(*it);
		make_heap(a.begin() + 1, a.end());
	}
	inline void operator = (const less_heap h)
	{
		a.clear();
		for (int i = 0; i < h.a.size(); i ++)
		a.push_back(h.a[i]);
	}
};