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

最小堆：任一结点的关键码均小于等于它的左右孩子的关键码，位于堆顶结点的关键码最小最大堆：任一结点的关键码均大于等于它的左右孩子的关键码，位于堆顶结点的关键码最大
//普通实现最小堆#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;}