堆結構：最大堆

“test.cpp”

#include
using namespace std;
#include
template
class Heap
{
public:
	Heap(T* arr,size_t size)
	{
		_arr.reserve(size);
		
		for(size_t i = 0;i < size;i++)
		{
			_arr.push_back(arr[i]);
		}
		
		//數組建堆
		for(int i = (_arr.size()-2)/2;i >= 0;--i)
		{
			AdjustDown(i);
		}
	}

	void Push(const T& data)
	{
		_arr.push_back(data);
		AdjustUp(_arr.size()-1);
	}
	//pop掉堆頂的數據
	void Pop()
	{
		//先使堆頂數據和最後一個數據交換，然後吧最後一個數據pop掉
		swap(_arr[0],_arr[_arr.size()-1]);
		_arr.pop_back();

		//原先的最後一個數據調至堆頂，然後除堆頂外左右子樹還是滿足大堆
		//所以此時只需要將堆頂的數據向下調整
		AdjustDown(0);

	}
	void Display()
	{
		for(size_t i = 0;i < _arr.size();i++)
		{
			cout<<_arr[i]<<" ";
		}
		cout< _arr[child])
			{
				++child;
			}

			if(_arr[child] > _arr[parent])
			{
				swap(_arr[child],_arr[parent]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}
	void AdjustUp(size_t root)
	{
		size_t child = root;
		size_t parent = (child-1)/2;

		while(parent >= 0)
		{
			if(_arr[child] > _arr[parent])
			{
				swap(_arr[child],_arr[parent]);
				child = parent;
				parent = (child-1)/2;
			}
			else
			{
				break;
			}
		}
	}
	size_t Size()
	{
		return _arr.size();
	}
	bool Empty()
	{
		return _arr.empty();
	}
	const T& Top()
	{
		return _arr[0];
	}
private:
	vector _arr;
};

void test()
{
	int arr[] = {10,11,13,12,16,18,15,17,14,19};
	int size = sizeof(arr)/sizeof(arr[0]);

	Heap hp(arr,size);
	hp.Display();

	hp.Push(20);
	hp.Display();

	hp.Pop();
	hp.Display();

	cout<<"size = "<