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

2023-09-25 17:00:07 137

#include usingnamespacestd; #defineLeft(i)i*2+1 #defineRight(i)i*2+2 #defineParent(i)(i-1)/2 voidMax_Heapify(inta[],intlength,inti) { intleft,right; left=Left(i); right=Right(i); intnum=i; if(lefta[i]) { num=left; } //此处逻辑判断出错，开始为elseif，发现不能正确排序，改为else之后正确 if(righta[num]) { num=right; } if(num!=i) { inttemp; temp=a[i]; a[i]=a[num]; a[num]=temp; Max_Heapify(a,length,num); } } //此处添加利用循环方式代替递归Max_Heapify的函数，该函数可以替代Max_Heapify //在某些情况下能取得更好的效果 voidMax_Heapify1(inta[],intlength,inti) { intleft,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); } } voidHeap_Sort(inta[],intlength) { Build_Max_Heap(a,length); inti; inttemp; for(i=length-1;i>=1;i--) { temp=a[i]; a[i]=a[0]; a[0]=temp; length-=1; Max_Heapify1(a,length,0); } }

#include #include"BuileMaxHeap.h" usingnamespacestd; #defineMAX100 templateclassPriorQueue { private: intlength; typea[MAX]; public: PriorQueue() { inti; length=0; for(i=0;ivoidPriorQueue::Init(typeb[],intlen) { inti; this->length=len; if(len<=0) { cout<<"Initfailed!"<voidPriorQueue::BuildMaxHeapQueue() { Build_Max_Heap(a,length); } templatetypePriorQueue::Maxnum() { if(length<=0) { cout<<"thequeueisempty!"<boolPriorQueue::DeleteMax() { if(length<=0) { cout<<"thequeueisempty!"<voidPriorQueue::IncreaseKey(inti,typekey) { intnum=i; if(key0&&a[Parent(num)]voidPriorQueue::Insert(typekey) { if(length>=MAX) { cout<<"thequeueisfullcan'taddmore!"<voidPriorQueue::Print() { inti; for(i=0;ivoidPriorQueue::Sort() { Heap_Sort(a,length); }

#include"PriorQueue.h" #include usingnamespacestd; intmain() { PriorQueuenode; intb[10]={4,1,3,2,16,9,10,14,8,7}; node.Init(b,10); inti; node.Print(); cout<

以上就是数据结构优先队列的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

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

热门推荐

随机推荐