C++实现大小堆

堆是一种数据结构，常用在内存中数据的存储，大小堆的存在便于我们寻找所需要的数据。

学习过大小堆后就尝试用C++来实现一个简易的大小堆。

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
template <class T>
class Heap
{
public:
	Heap()
	{}

	Heap(const T* array, size_t size)
	{
		_array.reserve(size);
		for (size_t i = 0; i < size; i++)
		{
			_array.push_back(array[i]);
		}
		/*for (int i = _array.size()-1; i >= _array.size()/ 2-1; --i)
		{
			_AdjustUp(i);
		}*///小堆
			for (int i = (_array.size() - 2) / 2; i >= 0; i--)
			{
				_AdjustDown(i);
			}//大堆
	}
	void Push(const T& data)
	{
		_array.push_back(10);
		/*for (int i = _array.size()-1; i >= _array.size()/ 2-1; --i)
		{
		_AdjustUp(i);
		}*///小堆
		for (int i = (_array.size() - 2) / 2; i >= 0; i--)
		{
			_AdjustDown(i);
		}//大堆
	}
	void Pop()
	{
		_array.pop_back();
		/*for (int i = _array.size()-1; i >= _array.size()/ 2-1; --i)
		{
		_AdjustUp(i);
		}*///小堆
		for (int i = (_array.size() - 2) / 2; i >= 0; i--)
		{
			_AdjustDown(i);
		}//大堆
	}
	T Top()const
	{
		return _array[0];
	}
	bool Empty()const
	{
		if (_array.size() != 0)
			return false;
		else
			return true;
	}
	size_t Size()const
	{
		return _array.size();
	}

private:
	void _AdjustDown(size_t parent)//大堆，上面大
	{
		size_t _parent = parent;
		size_t _child = _parent * 2;
		while (_child <= _array.size())
		{
			if (_child + 1 < _array.size() && _array[_child] < _array[_child + 1])
				_child++;
			if (_array[_child] > _array[_parent])
			{
				swap(_array[_child], _array[_parent]);
				_parent = _child;
				_child = _parent * 2 ;
			}
			else
				break;
		}
	}
	void _AdjustUp(size_t child)
	{
		size_t _child = child;
		size_t _parent = (_child-1) / 2;
		while (_child>=1)
		{
			if ( _array[child] > _array[_child -1])
				_child--;
			if (_array[_child] < _array[_parent])
			{
				swap(_array[_child], _array[_parent]);
				_child = _parent;
				_parent = (_child -1)/ 2;
			}
			else
				break;
		}
	}
private:
	std::vector<T> _array;
};
int main()
{
	int a[7] = { 7,3,5,1,6,8,2 };
	Heap<int> tree(a,7);
	//tree.Pop();
	tree.Push(10);
	return 0;
}