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 la[largest]:#下标从0~heap_size-1
   largest=l
  if ra[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 key0 and a[self.Parent(i)]            

            名称栏目：python实现最大优先队列-创新互联            

            标题链接：http://cdkjz.cn/article/cogipd.html