python实现最大优先队列
本文实例为大家分享了python实现最大优先队列的具体代码,供大家参考,具体内容如下
说明:为了增强可复用性,设计了两个类,Heap类和PriorityQ类,其中PriorityQ类继承Heap类,从而达到基于最大堆实现最大优先队列。
#!/usr/bin/envpython #coding=utf-8 classHeap(object): #求给定下标i的父节点下标 defParent(self,i): ifi%2==0: returni/2-1 else: returni/2 #求给定下标i的左孩子下标 defLeft(self,i): return2*i+1 #求给定下标i的右孩子下标 defRight(self,i): return2*i+2 #维护堆的性质:遵循最大堆 defMaxHeapify(self,a,i,heap_size): l=self.Left(i) r=self.Right(i) largest=i ifla[largest]:#下标从0~heap_size-1 largest=l ifr a[largest]: largest=r iflargest!=i:#若当前节点不是最大的,下移 a[i],a[largest]=a[largest],a[i]#交换a[i]和a[largest] self.MaxHeapify(a,largest,heap_size)#追踪下移的节点 #建堆 defBuildMaxHeap(self,a): heap_size=len(a) foriinrange(heap_size/2-1,-1,-1):#从最后一个非叶节点开始调整 #a[heap_size/2-1]~a[0]都是非叶节点,其他的是叶子节点 self.MaxHeapify(a,i,heap_size) #堆排序算法 defHeapSort(self,a): heap_size=len(a) '''step1:初始化堆,将a[0...n-1]构造为堆(堆顶a[0]为最大元素)''' self.BuildMaxHeap(a) foriinrange(len(a)-1,0,-1): #printa '''step2:将当前无序区的堆顶元素a[0]与该区间最后一个记录交换 得到新的无序区a[0...n-2]和新的有序区a[n-1],有序区的范围从 后往前不断扩大,直到有n个''' a[0],a[i]=a[i],a[0]#每次将剩余元素中的最大者放到最后面a[i]处 heap_size-=1 '''step3:为避免交换后新的堆顶违反堆的性质,因此将新的无序区调整为新 的堆''' self.MaxHeapify(a,0,heap_size) #最大优先队列的实现 classPriorityQ(Heap): #返回具有最大键字的元素 defHeapMaximum(self,a): returna[0] #去掉并返回具有最大键字的元素 defHeapExtractMax(self,a): heap_size=len(a) #ifheap_size<0: #error"heapunderflow" ifheap_size>0: max=a[0] a[0]=a[heap_size-1] #heap_size-=1#该处不对,并没有真正实现数组长度减一 dela[heap_size-1]#!!!!!! self.MaxHeapify(a,0,len(a)) returnmax #将a[i]处的关键字增加到key defHeapIncreaseKey(self,a,i,key): ifkey0anda[self.Parent(i)] 测试结果:
BigHeap1:[100,98,23,89,34,-5,6,11,0,2,4] Maximun:100 ExtractMax:100 BigHeap2:[98,89,23,11,34,-5,6,4,0,2] newkeyissmallerthancurrentone [98,89,23,11,34,-5,6,4,0,2] [98,89,30,11,34,-5,6,4,0,2] [100,98,30,11,89,-5,6,4,0,2,34]以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。