python实现最大优先队列

 更新时间:2019年08月29日 10:04:20   作者:爱橙子的OK绷   我要评论
这篇文章主要为大家详细介绍了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]

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持澳门金沙网上娱乐。

相关文章

  • python实现ip地址查询经纬度定位详解

    python实现ip地址查询经纬度定位详解

    这篇文章主要介绍了python实现ip地址查询经纬度定位详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
    2019-08-08
  • python使用tensorflow深度学习识别验证码

    python使用tensorflow深度学习识别验证码

    这篇文章主要介绍了python使用tensorflow深度学习识别验证码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2018-04-04
  • python中sets模块的用法实例

    python中sets模块的用法实例

    这篇文章主要介绍了python中sets模块的用法实例,该模块用来处理集合类型的数据,在这个模块中提供了两个集合类:Set(可变集合)和ImmurableSet(不可变集合),本文实例主要分析了Set(可变集合)的用法,需要的朋友可以参考下
    2014-09-09
  • Python常用字符串替换函数strip、replace及sub用法示例

    Python常用字符串替换函数strip、replace及sub用法示例

    这篇文章主要介绍了Python常用字符串替换函数strip、replace及sub用法,结合实例形式分析了Python针对字符串替换的常用函数strip、replace及sub功能及简单使用技巧,需要的朋友可以参考下
    2018-05-05
  • python字典DICT类型合并详解

    python字典DICT类型合并详解

    这篇文章主要为大家详细介绍了python字典DICT类型合并,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-08-08
  • Python基于sftp及rsa密匙实现远程拷贝文件的方法

    Python基于sftp及rsa密匙实现远程拷贝文件的方法

    这篇文章主要介绍了Python基于sftp及rsa密匙实现远程拷贝文件的方法,结合实例形式分析了基于RSA秘钥远程登陆及文件操作的相关技巧,需要的朋友可以参考下
    2016-09-09
  • 解决pandas .to_excel不覆盖已有sheet的问题

    解决pandas .to_excel不覆盖已有sheet的问题

    今天小编就为大家分享一篇解决pandas .to_excel不覆盖已有sheet的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-12-12
  • Python使用matplotlib和pandas实现的画图操作【经典示例】

    Python使用matplotlib和pandas实现的画图操作【经典示例】

    这篇文章主要介绍了Python使用matplotlib和pandas实现的画图操作,结合实例形式分析了Python基于matplotlib和pandas的数值运算与图形显示操作相关实现技巧,并对部分代码的图形显示进行了显示效果测试,需要的朋友可以参考下
    2018-06-06
  • python验证身份证信息实例代码

    python验证身份证信息实例代码

    这篇文章主要介绍了python验证身份证信息的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2019-05-05
  • Django 接收Post请求数据,并保存到金沙国际官网的实现方法

    Django 接收Post请求数据,并保存到金沙国际官网的实现方法

    今天小编就为大家分享一篇Django 接收Post请求数据,并保存到金沙国际官网的实现方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-07-07

最新评论