#pragmaonce#include<vector>#include<assert.h>////小堆==大堆//仿函数//template<classT>structGreater{booloperator()(constT&l,constT&r){returnl>r;}};template<classT>structLess{booloperator()(constT&l,constT&r){returnl<r;}};template<classT,classCompare=Less<T>>classHeap{public:Heap(){}Heap(constT*a,size_tsize){for(size_ti=0;i<size;++i){_array.push_back(a[i]);}//构建堆for(inti=(_array.size()-2)/2;i>=0;--i){AdjustDown(i);}}voidPush(constT&x){_array.push_back(x);AdjustUp(_array.size()-1);}voidPop(){assert(_array.size()>0);swap(_array[0],_array[_array.size()-1]);_array.pop_back();AdjustDown(0);}voidAdjustDown(intparent){intchild=parent*2+1;while(child<_array.size()){//找左右里面小的那一个//if(child+1<_array.size()//&&_array[child+1]>_array[child])if(child+1<_array.size()&&Compare()(_array[child+1],_array[child])){++child;}//小的孩子节点跟父节点比较//if(_array[child]>_array[parent])if(Compare()(_array[child],_array[parent])){swap(_array[child],_array[parent]);parent=child;child=2*parent+1;}else{break;}}}voidAdjustUp(intchild){intparent=(child-1)/2;//while(parent>=0)//?parent不会小于0while(child>0){//if(_array[child]>_array[parent])if(Compare()(_array[child],_array[parent])){swap(_array[child],_array[parent]);child=parent;parent=(child-1)/2;}else{break;}}}intSize(){return_array.size();}boolEmpty(){return_array.empty();}constT&Top(){return_array[0];}protected:vector<T>_array;//函数指针};voidTest1(){intarray[10]={10,16,18,12,11,13,15,17,14,19};Heap<int,Less<int>>hp1(array,10);hp1.Push(5);hp1.Pop();Heap<int,Greater<int>>hp2(array,10);hp2.Push(100);hp2.Pop();}template<classT,classCompare=Less<T>>classPriorityQueue{public:voidPush(constT&x){_queue.Push(x);}voidPop(){_queue.Pop();}constT&Top(){return_queue.Top();}protected:Heap<T,Compare>_queue;};//template<classT>//boolGreater(constT&l,constT&r);//仿函数voidTest2(){inta1=10,a2=20;Greater<int>GreaterFunc;Less<int>LessFunc;cout<<GreaterFunc(a1,a2)<<endl;cout<<LessFunc(a1,a2)<<endl;cout<<Greater<int>()(a1,a2)<<endl;cout<<Less<int>()(a1,a2)<<endl;}

以上