python实现最大优先队列
作者:爱橙子的OK绷 时间:2022-12-24 00:48:13
本文实例为大家分享了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
标签:python,最大优先队列


猜你喜欢
PyQt5使用mimeData实现拖拽事件教程示例解析下
2021-02-15 11:09:03

asp入门之字符串函数介绍示例
2008-11-04 20:18:00
python在windows下创建隐藏窗口子进程的方法
2021-05-19 14:44:51
Python一行代码识别增值税发票实现示例
2022-07-10 04:36:48

MySQL的一些安全注意点
2008-12-24 16:29:00
python实现大量图片重命名
2023-12-26 07:20:56
Python查找算法之插补查找算法的实现
2021-03-12 08:16:57

分享20个数据库设计的最佳实践
2024-01-24 09:28:53
Tensorflow实现卷积神经网络的详细代码
2022-02-20 22:14:06
解决Jupyter Notebook使用parser.parse_args出现错误问题
2023-05-09 17:41:42
PHP5中新增stdClass 内部保留类
2024-05-09 14:47:55
Python for Informatics 第11章 正则表达式(一)
2021-01-27 06:43:43
Oracle 下医嘱执行函数
2009-03-02 10:49:00
python中如何使用正则表达式提取数据
2023-12-09 17:24:21

Python监控服务器实用工具psutil使用解析
2021-10-14 03:16:24
Python基础知识之变量的详解
2023-12-16 13:41:40

浅谈MySQL在cmd和python下的常用操作
2024-01-16 13:11:17
eclipse创建python项目步骤详解
2021-01-15 00:40:47

分析SQL语句性能3种方法分享
2024-01-14 23:15:57

认清区别CSS的类class和id
2007-10-08 12:02:00