#include<iostream>usingnamespacestd;#include<vector>#include<assert.h>//仿函数template<classT>structLess{booloperator()(constT&left,constT&right){returnleft<right;}};template<classT>structGreater{booloperator()(constT&left,constT&right){returnleft>right;}};template<classT,classCompare=Less<T>>//默认为小堆classHeap{public:Heap(){}Heap(constT*array,size_tsize){for(size_ti=0;i<size;++i){_a.push_back(array[i]);}for(inti=(_a.size()-2)/2;i>=0;--i){_AdjustDown(i);}}voidPush(constT&x){_a.push_back(x);_AdjustUp(_a.size()-1);}voidPop(){assert(!_a.empty());swap(_a[0],_a[_a.size()-1]);_a.pop_back();_AdjustDown(0);}T&GetTop(){assert(!_a.empty());return_a[0];}boolEmpty(){return_a.empty();}size_tSize(){return_a.size();}voidPrint(){for(size_ti=0;i<_a.size();++i){cout<<_a[i]<<"";}cout<<endl;}protected://向下调整void_AdjustDown(size_tparent){Comparecompare;size_tchild=parent*2+1;while(child<_a.size()){//比较左右孩子if(child+1<_a.size()&&compare(_a[child+1],_a[child])){++child;}if(compare(_a[child],_a[parent])){swap(_a[child],_a[parent]);parent=child;child=parent*2+1;}else{break;}}}//向上调整void_AdjustUp(size_tchild){Comparecompare;size_tparent=(child-1)/2;while(child>0){if(compare(_a[child],_a[parent])){swap(_a[parent],_a[child]);child=parent;parent=(child-1)/2;}else{break;}}}protected:vector<T>_a;};voidTest(){inta[10]={10,11,13,12,16,18,15,17,14,19};Heap<int,Greater<int>>hp1(a,sizeof(a)/sizeof(a[0]));hp1.Print();cout<<"size:"<<hp1.Size()<<endl;cout<<"top:"<<hp1.GetTop()<<endl;cout<<"empty:"<<hp1.Empty()<<endl;}intmain(){Test();return0;}