python实现最大优先队列
程序员文章站
2023-08-13 22:42:42
本文实例为大家分享了python实现最大优先队列的具体代码,供大家参考,具体内容如下
说明:为了增强可复用性,设计了两个类,heap类和priorityq类,其中prio...
本文实例为大家分享了python实现最大优先队列的具体代码,供大家参考,具体内容如下
说明:为了增强可复用性,设计了两个类,heap类和priorityq类,其中priorityq类继承heap类,从而达到基于最大堆实现最大优先队列。
#! /usr/bin/env python #coding=utf-8 class heap(object): #求给定下标i的父节点下标 def parent(self, i): if i%2==0: return i/2 - 1 else: return i/2 #求给定下标i的左孩子下标 def left(self, i): return 2*i+1 #求给定下标i的右孩子下标 def right(self, i): return 2*i+2 #维护堆的性质:遵循最大堆 def maxheapify(self, a, i, heap_size): l=self.left(i) r=self.right(i) largest = i if l<heap_size and a[l]>a[largest]:#下标从0~heap_size-1 largest=l if r<heap_size and a[r]>a[largest]: largest=r if largest!=i:#若当前节点不是最大的,下移 a[i], a[largest] = a[largest], a[i]#交换a[i]和a[largest] self.maxheapify(a, largest, heap_size)#追踪下移的节点 #建堆 def buildmaxheap(self, a): heap_size=len(a) for i in range(heap_size/2 - 1, -1, -1):#从最后一个非叶节点开始调整 #a[heap_size/2 - 1]~a[0]都是非叶节点,其他的是叶子节点 self.maxheapify(a, i, heap_size) #堆排序算法 def heapsort(self, a): heap_size=len(a) '''step1:初始化堆,将a[0...n-1]构造为堆(堆顶a[0]为最大元素)''' self.buildmaxheap(a) for i in range(len(a)-1, 0, -1): #print a '''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) #最大优先队列的实现 class priorityq(heap): #返回具有最大键字的元素 def heapmaximum(self, a): return a[0] #去掉并返回具有最大键字的元素 def heapextractmax(self, a): heap_size=len(a) #if heap_size<0: # error "heap underflow" if heap_size>0: max=a[0] a[0]=a[heap_size-1] #heap_size -= 1 #该处不对,并没有真正实现数组长度减一 del a[heap_size-1]#!!!!!! self.maxheapify(a, 0, len(a)) return max #将a[i]处的关键字增加到key def heapincreasekey(self, a, i, key): if key<a[i]: print "new key is smaller than current one" else: a[i]=key '''当前元素不断与其父节点进行比较,如果当前元素关键字较大,则与其 父节点进行交换。不断重复此过程''' while i>0 and a[self.parent(i)]<a[i]: a[i], a[self.parent(i)] = a[self.parent(i)], a[i] i=self.parent(i) #增加元素 def maxheapinsert(self, a, key): #heap_size=len(a) #heap_size += 1 #a[heap_size-1]=-65535 a.append(-65535)#在a的末尾增加一个关键字为负无穷的叶节点扩展最大堆 heap_size=len(a) self.heapincreasekey(a, heap_size-1, key) if __name__ == '__main__': h = heap() p = priorityq() x = [0, 2, 6, 98, 34, -5, 23, 11, 89, 100, 4] #x1= [3,9,8,4,5,2,10,18] #h.heapsort(x) #h.heapsort(x1) #print x #print x1 h.buildmaxheap(x)#首先建立大顶堆 print '%s %r' % ('bigheap1:', x) # %r是万能输出格式 print '%s %d' % ('maximun:', p.heapmaximum(x)) print '%s %d' % ('extractmax:', p.heapextractmax(x)) print '%s %r' % ('bigheap2:', x) #p.maxheapinsert(x, 100) #print x p.heapincreasekey(x, 2, 20) print x p.heapincreasekey(x, 2, 30) print x p.maxheapinsert(x, 100) print x
测试结果:
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] new key is smaller than current one [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]
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
上一篇: laravel框架中表单请求类型和CSRF防护实例分析
下一篇: 个性验证码的制作方法