python实现最大优先队列


						本文实例为大家分享了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]



以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持中文源码网。