复制代码代码如下:
# -*- coding: utf-8 -*-
class Heap(object):
@classmethod
def parent(cls, i):
"""父结点下标"""
return int((i - 1) >> 1);
@classmethod
def left(cls, i):
"""左儿子下标"""
return (i << 1) + 1;
@classmethod
def right(cls, i):
"""右儿子下标"""
return (i << 1) + 2;
class MinPriorityQueue(list, Heap):
@classmethod
def min_heapify(cls, A, i, heap_size):
"""最小堆化A[i]为根的子树"""
l, r = cls.left(i), cls.right(i)
if l < heap_size and A[l] < A[i]:
least = l
else:
least = i
if r < heap_size and A[r] < A[least]:
least = r
if least != i:
A[i], A[least] = A[least], A[i]
cls.min_heapify(A, least, heap_size)
def minimum(self):
"""返回最小元素，伪码如下：
HEAP-MINIMUM(A)
1 return A[1]
T(n) = O(1)
"""
return self[0]
def extract_min(self):
"""去除并返回最小元素，伪码如下：
HEAP-EXTRACT-MIN(A)
1 if heap-size[A] < 1
2 then error "heap underflow"
3 min ← A[1]
4 A[1] ← A[heap-size[A]] // 尾元素放到第一位
5 heap-size[A] ← heap-size[A] - 1 // 减小heap-size[A]
6 MIN-HEAPIFY(A, 1) // 保持最小堆性质
7 return min
T(n) = θ(lgn)
"""
heap_size = len(self)
assert heap_size > 0, "heap underflow"
val = self[0]
tail = heap_size - 1
self[0] = self[tail]
self.min_heapify(self, 0, tail)
self.pop(tail)
return val
def decrease_key(self, i, key):
"""将i处的值减少到key，伪码如下：
HEAP-DECREASE-KEY(A, i, key)
1 if key > A[i]
2 then error "new key is larger than current key"
3 A[i] ← key
4 while i > 1 and A[PARENT(i)] > A[i] // 不是根结点且父结点更大时
5 do exchange A[i] ↔ A[PARENT(i)] // 交换两元素
6 i ← PARENT(i) // 指向父结点位置
T(n) = θ(lgn)
"""
val = self[i]
assert key <= val, "new key is larger than current key"
self[i] = key
parent = self.parent
while i > 0 and self[parent(i)] > self[i]:
self[i], self[parent(i)] = self[parent(i)], self[i]
i = parent(i)
def insert(self, key):
"""将key插入A，伪码如下：
MIN-HEAP-INSERT(A, key)
1 heap-size[A] ← heap-size[A] + 1 // 对元素个数增加
2 A[heap-size[A]] ← +∞ // 初始新增加元素为+∞
3 HEAP-DECREASE-KEY(A, heap-size[A], key) // 将新增元素减少到key
T(n) = θ(lgn)
"""
self.append(float('inf'))
self.decrease_key(len(self) - 1, key)
if __name__ == '__main__':
import random
keys = range(10)
random.shuffle(keys)
print(keys)
queue = MinPriorityQueue() # 插入方式建最小堆
for i in keys:
queue.insert(i)
print(queue)
print('*' * 30)
for i in range(len(queue)):
val = i % 3
if val == 0:
val = queue.extract_min() # 去除并返回最小元素
elif val == 1:
val = queue.minimum() # 返回最小元素
else:
val = queue[1] - 10
queue.decrease_key(1, val) # queue[1]减少10
print(queue, val)
print([queue.extract_min() for i in range(len(queue))])
您可能感兴趣的文章:
python异步任务队列示例
python计算最大优先级队列实例
Python下的Mysql模块MySQLdb安装详解
Python 分析Nginx访问日志并保存到MySQL数据库实例
python连接mysql调用存储过程示例
python Django连接MySQL数据库做增删改查
Python操作Mysql实例代码教程在线版(查询手册)
Python查询Mysql时返回字典结构的代码
python操作MySQL数据库的方法分享
python基于mysql实现的简单队列以及跨进程锁实例详解
QQ空间 搜狐微博 人人网 开心网 百度搜藏更多
Tags：python 优先级队列
复制链接收藏本文打印本文关闭本文返回首页
上一篇：python查找第k小元素代码分享
下一篇：python基于mysql实现的简单队列以及跨进程锁实例详解
相关文章
2014-07-07Python实现端口复用实例代码
2013-11-11python计算程序开始到程序结束的运行时间和程序运行的CPU时间
2014-07-07python采用requests库模拟登录和抓取数据的简单示例
2014-07-07python设置检查点简单实现代码
2013-01-01python连接sql server乱码的解决方法
2013-02-02用python实现的去除win下文本文件头部BOM的代码
2014-03-03pyqt4教程之实现半透明的天气预报界面示例
2013-03-03python实现的各种排序算法代码
2014-04-04python实现simhash算法实例
2013-12-12用python写asp详细讲解
文章评论
最 近 更 新
python使用beautifulsoup从爱奇艺网抓取视
python类定义的讲解
python网络编程学习笔记(八)：XML生成与解
python 判断自定义对象类型
Python time模块详解（常用函数实例讲解,
从零学python系列之浅谈pickle模块封装和
python定时检查启动某个exe程序适合检测e
python练习程序批量修改文件名
测试、预发布后用python检测网页是否有日
Python 错误和异常小结
热 点 排 行
Python入门教程 超详细1小时学会
python 中文乱码问题深入分析
比较详细Python正则表达式操作指
Python字符串的encode与decode研
Python open读写文件实现脚本
Python enumerate遍历数组示例应
Python 深入理解yield
Python+Django在windows下的开发
python 文件和路径操作函数小结
python 字符串split的用法分享