/*
*文件说明:堆的相关声明及实现(第二遍)
*作者:高小调
*日期:2016-12-27
*集成开发环境:Microsoft Visual Studio 2010 
*/
#include<vector>
template<typename T>
struct Min{
	bool operator()(T left,T right){
		return left<right;
	}
};
template<typename T>
struct Max{
	bool operator()(T left,T right){
		return left>right;
	}
};

template<typename T,typename class Type = Min<T>>
class Heap{
public:
	Heap(){}
	Heap(T arr[],size_t sz)
		:_a(arr,arr+sz){
		size_t LastNotLeapNode = (_a.size()-2)/2;
		for(int idx=LastNotLeapNode; idx>=0; --idx){
			_AdjustDown(idx);
		}
	}

	void Push(const T &e){
		_a.push_back(e);
		size_t LastNotLeapNode = (_a.size()-2)/2;
		_AdjustUp(LastNotLeapNode);
	}
	
	void Pop(){
		swap(_a[0],_a[_a.size()-1]);
		_a.pop_back();
		_AdjustDown(0);
	}
protected:

	void _AdjustDown(size_t idx){
		size_t parent = idx;
		size_t child = idx*2+1;
		while(child<_a.size()){

			if(child+1<_a.size() && Type()(_a[child+1],_a[child])){
				++child;	
			}

			if(Type()(_a[child],_a[parent])){
				swap(_a[child],_a[parent]);
				parent = child;
				child = parent*2+1;
			}else{
				break;
			}

		}
	}

	void _AdjustUp(size_t idx){
		size_t parent = idx;
		size_t child = 2*idx+1;
		while(child<_a.size() && child>parent){

			if(child+1<_a.size() && Type()(_a[child+1] , _a[child])){
				++child;
			}

			if(Type()(_a[child],_a[parent])){
				swap(_a[child],_a[parent]);
				child = parent;
				parent = (child-1)/2;
			}else{
				break;	
			}
		
		}
	}

private:
	vector<T> _a;
};

/*
*文件说明:测试文件
*作者:高小调
*日期:2016-12-26
*集成开发环境:Microsoft Visual Studio 2010 
*/
#include<iostream>
using namespace std;
#include"Heap2.h"
void TestHeap(){
	int arr[] = {10,16,18,12,11,13,15,17,14,19};
	size_t sz = sizeof(arr)/sizeof(arr[0]);
	Heap<int> h1(arr,sz);			//小堆
	Heap<int,Max<int>> h2(arr,sz);	//大堆
	h1.Pop();
	h1.Push(5);
	h2.Pop();
	h2.Push(20);
}
int main(){
	TestHeap();
	return 0;
}