代码按照适配器模式实现，若理解了堆的内部怎么实现的，那优先级的队列实现则是非常简单的了，堆的设计大家不明白的话，可以查看我的博客http://10740184.blog.51cto.com/10730184/1767076。


建立PriorityQueue.hpp：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<assert.h>#include<vector>template<classT>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():_a(NULL){}Heap(constT*a,size_tsize){for(inti=0;i<size;i++){_a.push_back(a[i]);}for(inti=(size-2)/2;i>=0;i--){_adjustDown(i);}}void_adjustDown(size_tparent){Compare<T>com;size_tchild=2*parent+1;size_tsize=_a.size();while(child<size){if(child+1<size&&com(_a[child+1],_a[child])){++child;}if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);parent=child;child=2*parent+1;}else{break;}}}voidPush(constT&x){_a.push_back(x);_adjustUp(_a.size()-1);}void_adjustUp(size_tchild){intparent=(child-1)/2;Compare<T>com;while(child>0){if(com(_a[child],_a[parent])){swap(_a[parent],_a[child]);child=parent;parent=(child-1)/2;}else{break;}}}size_tSize(){size_tsize=_a.size();returnsize;}boolEmpty(){assert(Size()>=0);returnSize()==0;}voidPop(){assert(_a.Size()>0);swap(_a[0],_a[Size-1]);_a.pop_back();_adjustDown(0);}T&GetTop(){return_a[0];}voidPrint(){cout<<"大堆序列："<<endl;for(inti=0;i<_a.size();i++){cout<<_a[i]<<"";}cout<<endl;}public:vector<T>_a;};template<classT,template<class>classCompare=Less>classPriorityQueue{public:voidPush(constT&x){_hp.Push(x);}voidPop(){_hp.Pop();}size_tSize(){return_hp.Size();}boolEmpty(){_hp.Empty();}T&Top(){return_hp.GetTop();}voidPrint(){_hp.Print();}private:Heap<T,Compare>_hp;};


建立PriorityQueue.cpp文件：

#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#include"PriorityQueue.hpp"voidTest(){inta[]={10,11,13,12,16,18,15,17,14,19};PriorityQueue<int,Greater>pq;pq.Push(10);pq.Push(11);pq.Push(13);pq.Push(12);pq.Push(16);pq.Push(18);pq.Push(15);pq.Push(17);pq.Push(14);pq.Push(19);pq.Print();}intmain(){Test();system("pause");return0;}