堆的简单实现（仿函数）

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

堆结构的二叉树存储是：

代码实现如下：

#pragma once #include <iostream> #include <vector> #include <assert.h> using namespace std; //仿函数 template <typename T> struct Greater {	bool operator() (const T & l, const T & r)	{	return l > r;	} }; template <typename T> struct Less {	bool operator() (const T & l, const T & r)	{	return l < r;	} }; //模板参数 template <typename T,typename comer=Greater<T> > class Heap { public:	//无参构造函数	Heap()	:_a(NULL)	{}	//有参构造函数	Heap(T * a, size_t size)	{	assert(a);	//先把数据保存在vector中	for (size_t i = 0; i < size; i++)	{	_a.push_back(a[i]);	}	//建堆	for (int j = ((_a.size() - 2) / 2); j >= 0; j--)	{	//向下调整算法	_AdjustDown(j);	}	}	void Push(const T x)//插入元素	{	_a.push_back(x);	_AdjustUp(_a.size() - 1);	}	void Pop()//删除元素	{	assert(_a.size() > 0);	swap(_a[0], _a[_a.size() - 1]);	_a.pop_back();	_AdjustDown(0);	}	size_t Size()	{	return _a.size();	}	bool Empty()	{	return _a.empty();	}	void print()	{	for (int i = 0; i < _a.size(); i++)	{	cout << _a[i] << " ";	}	cout << endl;	} protected:	//向下调整算法	void _AdjustDown(size_t parent)	{	size_t child = parent * 2 + 1;	comer com;	while (child < _a.size())	{	//找出左右孩子中比较大的	if (child + 1 < _a.size() && com(_a[child + 1] , _a[child]))	{	child++;	}	//比较父亲和孩子的大小	if (com (_a[child],_a[parent]))	{	swap(_a[child], _a[parent]);	parent = child;	child = parent * 2 + 1;	}	else	{	break;	}	}	}	//向上调整算法	void _AdjustUp(size_t child)	{	assert(child < _a.size());	int parent = (child - 1) / 2;	comer com;	while (child > 0)	{	//只需看父节点<根节点	if (com(_a[child], _a[parent]))	{	swap(_a[child], _a[parent]);	child = parent;	parent = (child - 1) / 2;	}	else	{	break;	}	}	} private:	vector <T> _a; };

需要学习的也就是向上以及向下调整算法。

欢迎大家提出宝贵的意见。

测试用例如下：

void Test() {	int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };	Heap<int,Less<int> > hp1(a, sizeof(a) / sizeof(a[0]));	hp1.print();	cout << hp1.Size() << endl;	cout << hp1.Empty() << endl;	hp1.Push(20);	hp1.print();	cout << hp1.Size() << endl;	cout << hp1.Empty() << endl;	hp1.Pop();	hp1.print();	cout << hp1.Size() << endl;	cout << hp1.Empty() << endl;