python实现最大优先队列
作者:爱橙子的OK绷 发布时间:2022-12-24 00:48:13
标签: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]
来源:https://blog.csdn.net/will130/article/details/44659769
0
投稿
猜你喜欢
- numpy的delete是可以删除数组的整行和整列的,下面简单介绍和举例说明delete函数用法:numpy.delete(arr, obj
- 很多时候,查看一个文件夹下的每个文件大小可以轻易的做到,因为文件后面就是文件尺寸,但是如果需要查看一个文件夹下面所有的文件夹对应的尺寸,就发
- 在家无聊,线代和高数看不懂,整点事情干,就准备预定回学校的高铁票,于是就有了这个文章准备工作1.pip安装chromediver,当然也可以
- 为了庆祝自己的博客重新开放,我在这里放一个自己刚刚写的jquery日期插件, 也许人们会说:日期选取插件已
- 今天我们来学习用 Web 标准的方法来制作 Google 首页(中文)。Google 首页一直是用 table 布局的。我们把 Google
- 函数局部变量 全局变量 及其作用域#简单类型(int str等)变量的局部变量与全局变量及其作用域的关系name = "xxx&q
- JSP 开发之 releaseSession的实例详解Hibernate可以实现分页查询,昨天试了一下,分页效果不错。但是发现了一个问题,就
- 为了得到更加清晰的图像我们需要通过技术对图像进行处理,比如使用对比度增强的方法来处理图像,对比度增强就是对图像输出的灰度级放大到指定的程度,
- rs.open sql,conn:如果sql是delete,update,insert则会返
- 如何实现优惠打折? 代码及说明见下:<%@ LANG
- image.jsp------------------------------生成随机验证码图片的Jsp页面 代码如下: <
- numpy官方文档meshgrid函数帮助文档https://docs.scipy.org/doc/numpy/reference/gene
- 本文实例讲述了python实现根据窗口标题调用窗口的方法。分享给大家供大家参考。具体分析如下:当你知道一个windows窗口的标题后,可以用
- 本文实例讲述了Python实现的各种常见分布算法。分享给大家供大家参考,具体如下:#-*- encoding:utf-8 -*-import
- 品牌是我们一直挂在嘴边的词语,视觉设计师们经常说到,公司的品牌该如何如何去设计?这个违背了我们的公司品牌!等等。之前我有谈过关于 品牌灵魂的
- MongoDB是一个文档型数据库,是NOSQL家族中最重要的成员之一,以下代码封装了MongoDB的基本操作。MongoDBConfig.j
- 本文实例讲述了用python实现面向对像的ASP程序的方法。分享给大家供大家参考。具体实现方法如下:平时我们写ASP时,一般都用vbscri
- 前言如果你以前没有接触过面向对象的编程语言,那你可能需要先了解一些面向对象语言的一些基本特征,在头脑里头形成一个基本的面向对象的概念,这样有
- 内容摘要:当讨论Request对象内容时,要研究的集合之一就是ServerVariables集合。这个集合包含了两种值的结合体,一种是随同页
- 防止一般的采集以及小偷读取,加在顶部。同理,可以改造成JS脚本。下面的方法是通过选择同一IP的访问频率来达到防止采集的目的,就是可能也把搜索