堆的创建、插入、删除，模板参数实现堆以及模板的模板参数实现堆

最小堆：任一结点的关键码均小于等于它的左右孩子的关键码，位于堆顶结点的关键码最
小
最大堆：任一结点的关键码均大于等于它的左右孩子的关键码，位于堆顶结点的关键码
最
大
//普通实现最小堆
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
using namespace std;
#include<stdlib.h>
#include<vector>
#include<assert.h>
template<class T>
class Heap
{
public:
	Heap()
	{}
	Heap(const T array[], size_t size)
	{
		size_t i = 0;
		for (i = 0; i < size; i++)
		{
			_heap.push_back(array[i]);
		}
		//找到最后一个非叶子节点
		size_t root = (size - 2) / 2;
		for (i = root; i>0; i--)
		{
			AdJustDown(i,size);
		}
	}
	//在堆中插入元素
	void Insert(const T& data)
	{
		_heap.push_back(data);
		size_t size = _heap.size();
		if (size > 0)
		{
			AdJustUp(size);
		}
	}

	//移除堆顶元素
	void Remove()
	{
		//assert(!Empty());
		assert(!Empty());
		size_t size = _heap.size();
		if (size > 1)
		{
			std::swap(_heap[0],_heap[size-1]);
			_heap.pop_back();
			AdJustDown(0, size - 1);
		}
		else
		{
			_heap.pop_back();
		}
	}

	//判断堆是否为空
	bool Empty()const
	{
		return _heap.empty();
	}

	//求堆大小
	size_t Size()const
	{
		return _heap.size();
	}
PRivate:
	//从上往下调整顺序
	void AdJustDown(size_t root, size_t size)
	{
		size_t parent = root;
		size_t child = root*2+1;
		while (child < size)
		{
			//如果右孩子存在且右孩子小于左孩子
			if (child + 1 < size &&_heap[child + 1] < _heap[child])
			{
				child = child + 1;
			}
			//如果孩子小于双亲结点
			else if (_heap[child] < _heap[parent])
			{
				std::swap(_heap[child], _heap[parent]);
				parent = child;
				child = (parent - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	//从下往上调整顺序
	void AdJustUp(size_t size)
	{
		size_t child = size-1;
		size_t parent = (size-2) / 2;
		while (child != 0)
		{
			//如果孩子小于双亲结点
			if (_heap[child] < _heap[parent])
			{
				std::swap(_heap[child], _heap[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
          else
          break;
		}
	}
private:
	std::vector<T> _heap;
};
void test()
{
	int array[] = {7,9,6,8,5,3,1,2};
	Heap<int> hp(array, sizeof(array) / sizeof(array[0]));
	hp.Insert(4);
	hp.Remove();
}
int main()
{
	test();
	system("pause");
	return 0;
}
//模板参数实现最大最小堆
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
using namespace std;
#include<stdlib.h>
#include<vector>
#include<assert.h>
template<class T>
class Less
{
public:
	bool Operator()(const T& left, const T& right)
	{
		return left < right;
	}
};
template<class T>
class Greater
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};
template<class T, class Compare = Greater<T>>
class Heap
{
public:
	Heap()
	{}
	Heap(const T array[], size_t size)
	{
	  int i = 0;
		for (i = 0; i < size; i++)
		{
			_heap.push_back(array[i]);
		}
		//找到最后一个非叶子节点
		size_t root = (size - 2) / 2;
		for (i = root; i>=0;--i)
		{
			AdJustDown(i, size);
		}
	}
	//在堆中插入元素
	void Insert(const T& data)
	{
		_heap.push_back(data);
		size_t size = _heap.size();
		if (size > 0)
		{
			AdJustUp(size);
		}
	}

	//移除堆顶元素
	void Remove()
	{
		//assert(!Empty());
		assert(!Empty());
		size_t size = _heap.size();
		if (size > 1)
		{
			std::swap(_heap[0], _heap[size - 1]);
			_heap.pop_back();
			AdJustDown(0, size - 1);
		}
		else
		{
			_heap.pop_back();
		}
	}

	//判断堆是否为空
	bool Empty()const
	{
		return _heap.empty();
	}

	//求堆大小
	size_t Size()const
	{
		return _heap.size();
	}
private:
	//从上往下调整顺序
	void AdJustDown(size_t root, size_t size)
	{
		size_t parent = root;
		size_t child = root * 2 + 1;
		while (child != 0)
		{
			//如果右孩子存在且右孩子小于左孩子
			if (child + 1 < size &&Compare()(_heap[child + 1] , _heap[child]))
			{
				child = child + 1;
			}
			//如果孩子小于双亲结点
			//else if (_heap[child] < _heap[parent])
		   else if (Compare()(_heap[child] , _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				parent = child;
				child = parent*2+1;
			}
			else
			{
				break;
			}
		}
	}

	//从下往上调整顺序
	void AdJustUp(size_t size)
	{
		size_t child = size - 1;
		size_t parent = (size - 2) / 2;
		while (child != 0)
		{
			//如果孩子小于双亲结点
			/*if (_heap[child] < _heap[parent])*/
			if (Compare()(_heap[child] , _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
            break;
		}
	}
private:
	std::vector<T> _heap;
};
void test()
{
	int array[] = { 7, 9, 6, 8, 5, 3, 1, 2 };
	Heap<int,Greater<int>> hp(array, sizeof(array) / sizeof(array[0]));
	hp.Insert(4);
	hp.Remove();
}
int main()
{
	test();
	system("pause");
	return 0;
}
//模板的模板参数实现最大最小堆
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
using namespace std;
#include<stdlib.h>
#include<vector>
#include<assert.h>
template<class T>
class Less
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left < right;
	}
};
template<class T>
class Greater
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};
template<class T,template<class> class Compare = Less>
class Heap
{
public:
	Heap()
	{}
	Heap(const T array[], size_t size)
	{
		size_t i = 0;
		for (i = 0; i < size; i++)
		{
			_heap.push_back(array[i]);
		}
		//找到最后一个非叶子节点
		size_t root = (size - 2) / 2;
		for (int i = root; i >= 0; --i)
		{
			AdJustDown(i, size);
		}
	}
	//在堆中插入元素
	void Insert(const T& data)
	{
		_heap.push_back(data);
		size_t size = _heap.size();
		if (size > 0)
		{
			AdJustUp(size);
		}
	}

	//移除堆顶元素
	void Remove()
	{
		//assert(!Empty());
		assert(!Empty());
		size_t size = _heap.size();
		if (size > 1)
		{
			std::swap(_heap[0], _heap[size - 1]);
			_heap.pop_back();
			AdJustDown(0, size - 1);
		}
		else
		{
			_heap.pop_back();
		}
	}

	//判断堆是否为空
	bool Empty()const
	{
		return _heap.empty();
	}

	//求堆大小
	size_t Size()const
	{
		return _heap.size();
	}
private:
	//从上往下调整顺序
	void AdJustDown(size_t root, size_t size)
	{
		size_t parent = root;
		size_t child = root * 2 + 1;
		while (child <size)
		{
			//如果右孩子存在且右孩子小于左孩子
			if (child + 1 < size &&Compare<T>()(_heap[child + 1], _heap[child]))
			{
				child = child + 1;
			}
			//如果孩子小于双亲结点
			//else if (_heap[child] < _heap[parent])
			else if (Compare<T>()(_heap[child], _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
			    parent=child;
				child=parent*2+1;
			}
			else
			{
				break;
			}
		}
	}

	//从下往上调整顺序
	void AdJustUp(size_t size)
	{
		size_t child = size - 1;
		size_t parent = (size - 2) / 2;
		while (child != 0)
		{
			//如果孩子小于双亲结点
			/*if (_heap[child] < _heap[parent])*/
			if (Compare<T>()(_heap[child], _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}
private:
	std::vector<T> _heap;
};
void test()
{
	int array[] = { 7, 9, 6, 8, 5, 3, 1, 2 };
	Heap<int, Less> hp(array, sizeof(array) / sizeof(array[0]));
	hp.Insert(4);
	hp.Remove();
}
int main()
{
	test();
	system("pause");
	return 0;
}