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]

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