一、用模版实现大小堆


如果不用模版的话，写大小堆，就需要分别实现两次，但是应用模版的话问题就简单多了，我们只需要实现两个仿函数，Greater和Less就行了，仿函数就是用类实现一个()的重载就实现了仿函数。这个看下代码就能理解了。再设计参数的时候，需要把模版设计成模版的模版参数，因为要实现大小堆嘛！当我们实现好一个大堆或者小队的逻辑后只需要用模版接收的Greater或Less类定义一个变量，就能实现通用功能了。


template<typenameT>structLess{booloperator()(constT&l,constT&r){returnl<r;}};template<classT>structGreater{booloperator()(constT&l,constT&r){returnl>r;}};template<classT,template<class>classcompare=less>classHeap{public:Heap(){}Heap(T*a,size_tsize){size_tindex=0;while(index<size){_a.push_back(a[index]);index++;}for(inti=(_a.size()-2)/2;i>=0;i--)_AdjustDown(i);}voidpush(constT&x){_a.push_back(x);_AdjustUp(_a.size()-1);}voidpop(){size_tsize=_a.size();assert(size>0);swap(_a[0],_a[size-1]);_a.pop_back();size=_a.size();_AdjustDown(0);}size_ttop(){assert(!_a.empty());return_a[0];}boolempty(){return_a.size()==0;}size_tSize(){return_a.size();}voidPrint(){for(inti=0;i<_a.size();i++){cout<<_a[i]<<"";}cout<<endl;}protected:void_AdjustUp(intchild){intparent=(child-1)/2;compare<T>com;//如果是大堆传过来就是用大堆的逻辑，小堆就实现小堆的逻辑while(child>0){//找出孩子中的最大孩子if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}void_AdjustDown(size_tparent){size_tchild=2*parent+1;compare<T>com;//如果是大堆传过来就是用大堆的逻辑，小堆就实现小堆的逻辑while(child<_a.size()){//找出孩子中的最大孩子if(child+1<_a.size()&&com(_a[child+1],_a[child])){++child;}//把if(com(_a[child],_a[parent])){swap(_a[parent],_a[child]);parent=child;child=child*2+1;}else{break;}}}protected:vector<T>_a;};


二、用模版实现优先级队列


前面实现了大小堆，这里我们可以使用适配器，直接调用大小堆，来实现优先级队列。


template<classT,template<class>classcompare=Less>classpriorityQueue{private:Heap<T,compare>_hp;public:voidpush(constT&x){_hp.push(x);}voidpop(){_hp.pop();}T&Top(){return_hp.top();}voidPrint(){_hp.Print();}};


三、堆排序的实现


堆排序的实现简单思路，(升序)先构造出来一个大堆，调整堆后，将堆头和最后一个数据交换，最大值就换到了数组的最后，然后在调整堆，但是size需要减少1，因为最大的已经调整到最后，如果再加上它调整又会回到堆头。

int*&HeapSort(int*a,size_tsize){for(inti=(size-2)/2;i>=0;i--){_AdjustDown(a,size,i);}for(inti=0;i<size;i++){swap(a[0],a[size-i-1]);_AdjustDown(a,size-i-1,0);}returna;}