【数据结构】实现大小堆也叫二叉堆（类似c++中的优先队列）_二叉堆c语言链表实现

二叉堆：

是一种特殊的堆，依赖于完成完全二叉树和向量实现的。分为最大堆和最小堆。

最大堆：父节点的键值总是大于或等于任何一个子节点的键值。

最小堆：父节点的键值总是小于或等于任何一个子节点的键值。

存储：二叉树一般用数组来存储表示，在下面的实现中使用了STL中的vector。根节点在数组中的位置是0，第n个位置的左孩子下标为n*2+1，右孩子为2*n+2 ，当前孩子存在的前提是计算后下标要小于数组总个数。而用孩子结点的下标c,可以计算出双亲的下标(c-1)/2。

基本操作：可以进行插入结点，移除最小的结点，和返回最小的结点，返回当前堆中元素个数。

代码：这个是用模板参数实现，传入函数对象生成大小堆，默认小堆：

#ifndef _HEAP_H_
#define  _HEAP_H_
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;
 
// 仿函数小堆调用 
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 = Less<T>>
class Heap
{
public:
	Heap(){}
	Heap(const T arr[] , int size)
	{
		for (int i=0; i<size; ++i)
		{
			_heap.push_back(arr[i]);
		}
		int last = (size - 2)/2; 
		for (int i=last; last>=0; --last)
		{
			_AdjustDown(last, size);
		}
	}
	void Insert(const T data)
	{
		_heap.push_back(data);
		_AdjustUp(_heap.size());
	}
 
	T& Top()
	{
		assert(!_heap.empty());
 
		return _heap[0]; 
	}
	const T& Top()const
	{
		assert(!_heap.empty());
 
		return _heap[0]; 
	}
	void Remove()
	{
		int size = _heap.size();
		if (size > 1)
		{
			std::swap(_heap[0], _heap[size-1]);
			_heap.pop_back();
			_AdjustDown(0, _heap.size());
		}
		else
		{
			_heap.pop_back();
		}
	}
private:
	void _AdjustUp(int size)
	{
		int child = size - 1;
		int parent = (child-1)/2;
		while (child != 0)
		{
			// 孩子小于父亲
			if (Compare()(_heap[child], _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				child = parent;
				parent = (child - 1 )/2;
			}
			else
			{
				break;
			}
		}
	}
	void _AdjustDown(int root, int size)
	{
		int child = root*2 + 1;
		int parent = root;
 
		while (child < size)
		{
			if (child+1 < size && Compare()(_heap[child+1], _heap[child]) )
			{
				child += 1;
			}
			// 小 less 
			if (Compare()(_heap[child], _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				parent = child;
				child = child *2 + 1;
			}
			else
			{
				break;
			}
		}
	}
private:
	vector<T> _heap;
};
#endif _HEAP_H_

这个是用模板的模板参数实现：

#ifndef _HEAP_H_
#define  _HEAP_H_
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;
 
// 仿函数小堆调用 
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 arr[], int size)
	{
		for (int i=0; i<size; ++i)
		{
			_heap.push_back(arr[i]);
		}
		int root = (size - 2)/2;
		for (int i=root; i>=0; --i)
		{
			_AdjustDown(i, size);
		}
	}
 
	void Insert(const T& data)
	{
		_heap.push_back(data);
		_AdjustUp(_heap.size());
	}
 
	void Remove()
	{
		if (!_heap.empty())
		{
			if (_heap.size()>1)
			{
				std::swap(_heap[0], _heap[_heap.size()-1]);
				_heap.pop_back();
				_AdjustDown(0, _heap.size());
			}
			else
			{
				_heap.pop_back();
			}
		}
	}
	T& Top()
	{
	assert(!_heap.empty());
 
	return _heap[0]; 
	}
	const T& Top()const
	{
	assert(!_heap.empty());
 
	return _heap[0]; 
	}
private:
	void _AdjustUp(int size)
	{
		int child = size-1;
		int  parent= (child-1)/2;
		while (child != 0)
		{
			if (Compare<T>()(_heap[child], _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				child = parent;
				parent = (child-1)/2;
			}
			else
			{
				break;
			}
		}
	}
    void _AdjustDown(int root, int size)
	{
		int parent = root;
		int child = root*2 + 1;
 
		while (child < size)
		{
			if (child+1 < size && Compare<T>()(_heap[child+1],_heap[child]) )
			{
				child  = child+1;
			}
			if (Compare<T>()(_heap[child], _heap[parent]))
			{
				std::swap(_heap[child], _heap[parent]);
				parent = child;
				child = child*2 + 1;
			}
			else
			{
				break;
			}
		}
	}
 
	private:
	vector<T> _heap;
};
#endif _HEAP_H_