C++ 实现优先队列的简单实例

 #include using namespace std; #define Left(i) i*2+1 #define Right(i) i*2+2 #define Parent(i) (i-1)/2 void Max_Heapify(int a[],int length,int i) { int left,right; left=Left(i); right=Right(i); int num=i; if(lefta[i]) { num=left; } //此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确 if(righta[num]) { num=right; } if(num!=i) { int temp; temp=a[i]; a[i]=a[num]; a[num]=temp; Max_Heapify(a,length,num); } } //此处添加利用循环方式代替递归Max_Heapify的函数，该函数可以替代Max_Heapify //在某些情况下能取得更好 的效果 void Max_Heapify1(int a[],int length,int i) { int left,right,num=i,largest=i; left=Left(i); right=Right(i); while(1) { if(a[left]>a[num]&&lefta[largest]&&right=0;i--) { Max_Heapify1(a,length,i); } } void Heap_Sort(int a[],int length) { Build_Max_Heap(a,length); int i; int temp; for(i=length-1;i>=1;i-<mark style="color:transparent">来源gaodaimacom搞#^代%!码&网</mark>-) { temp=a[i]; a[i]=a[0]; a[0]=temp; length-=1; Max_Heapify1(a,length,0); } } 

 #include #include "BuileMaxHeap.h" using namespace std; #define MAX 100 template class PriorQueue { private: int length; type a[MAX]; public: PriorQueue () { int i; length=0; for(i=0;i<MAX;i++) { a[i]=0; } } ~PriorQueue() { } void BuildMaxHeapQueue(); void Init(type b[],int len); type Maxnum(); bool DeleteMax(); void IncreaseKey(int i,type key); void Insert(type key); void Print(); void Sort(); }; templatevoid PriorQueue::Init(type b[],int len) { int i; this->length=len; if(len<=0) { cout<<"Init failed !"<<endl; } for(i=0;i<len;i++) { a[i]=b[i]; } BuildMaxHeapQueue(); } templatevoid PriorQueue::BuildMaxHeapQueue() { Build_Max_Heap(a,length); } templatetype PriorQueue::Maxnum() { if(length<=0) { cout<<"the queue is empty!"<<endl; return -1; } return a[0]; } templatebool PriorQueue::DeleteMax() { if(length<=0) { cout<<"the queue is empty!"<<endl; return 0; } a[0]=a[length-1]; length-=1; Max_Heapify1(a,length,0); return 1; } templatevoid PriorQueue::IncreaseKey(int i,type key) { int num=i; if(key0&&a[Parent(num)]void PriorQueue::Insert(type key) { if(length>=MAX) { cout<<"the queue is full can't add more!"<<endl; return ; } length+=1; a[length-1]=key; IncreaseKey(length-1,key); } templatevoid PriorQueue::Print() { int i; for(i=0;i<length;i++) { cout<void PriorQueue::Sort() { Heap_Sort(a,length); } 

 #include"PriorQueue.h" #include using namespace std; int main() { PriorQueue node; int b[10]={4,1,3,2,16,9,10,14,8,7}; node.Init(b,10); int i; node.Print(); cout<<endl; cout<<node.Maxnum()<<endl; node.DeleteMax(); node.Print(); node.Insert(232); node.Sort(); node.Print(); return 0; }