Python实现一个优先级队列的方法
作者:David Beazley 发布时间:2022-12-03 14:44:54
问题
怎样实现一个按优先级排序的队列? 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素
解决方案
下面的类利用 heapq
模块实现了一个简单的优先级队列:
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
下面是它的使用方式:
>>> class Item:
... def __init__(self, name):
... self.name = name
... def __repr__(self):
... return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>
仔细观察可以发现,第一个 pop()
操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素( foo
和 grok
),pop 操作按照它们 * 入到队列的顺序返回的。
讨论
这一小节我们主要关注 heapq
模块的使用。 函数 heapq.heappush()
和 heapq.heappop()
分别在队列 _queue
上插入和删除第一个元素, 并且队列 _queue
保证第一个元素拥有最高优先级( 1.4 节已经讨论过这个问题)。 heappop()
函数总是返回”最小的”的元素,这就是保证队列pop操作返回正确元素的关键。 另外,由于 push 和 pop 操作时间复杂度为 O(log N),其中 N 是堆的大小,因此就算是 N 很大的时候它们运行速度也依旧很快。
在上面代码中,队列包含了一个 (-priority, index, item)
的元组。 优先级为负数的目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。
index
变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index
下标变量,可以确保元素按照它们插入的顺序排序。 而且, index
变量也在相同优先级元素比较的时候起到重要作用。
为了阐明这些,先假定 Item
实例是不支持排序的:
>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>
如果你使用元组 (priority, item)
,只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话,那么比较操作就会跟之前一样出错:
>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>
通过引入另外的 index
变量组成三元组 (priority, index, item)
,就能很好的避免上面的错误, 因为不可能有两个元素有相同的 index
值。Python 在做元组比较时候,如果前面的比较已经可以确定结果了, 后面的比较操作就不会发生了:
>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>
如果你想在多个线程中使用同一个队列,那么你需要增加适当的锁和信号量机制。 可以查看 12.3 小节的例子演示是怎样做的。
heapq
模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。
来源:https://python3-cookbook.readthedocs.io/zh_CN/latest/c01/p05_implement_a_priority_queue.html
猜你喜欢
- Pycurl包是一个libcurl的Python接口,由C语言编写的,功能强大,速度快。由于pycurl的属性和方法太多了,写这篇博文记录一
- 前言:NoxfileNox 默认在一个名为noxfile.py的文件中查找配置。在运行 nox 时,你可以使用 --noxfile参数指定其
- 京东购物车抢购商品1.Python的下载和安装这里由于我们代码是基于Python来执行的所以我们这里需要2个东西:一个是Python本身,另
- Python encode()方法encode() 方法为字符串类型(str)提供的方法,用于将 str 类型转换成 bytes 类型,这个
- time模块中的三种时间表示方式:时间戳结构化时间对象格式化时间字符串1.时间戳时间戳1970.1.1到指定时间到间隔,单位是秒import
- Python使用pandas导入xlsx格式的excel文件内容1. 基本导入在 Python中使用pandas导入.xlsx文件的方法是r
- 使用 Python 内建的defaultdict 方法可以轻松定义一个树的数据结构。简单的说树也可以是一个字典数据结构 def t
- Python字符串问题在arcpy中版本为 python2.x在QGIS中版本为 python2.x 或者 python3.xpython2
- 前言说说外星人那些事儿....你以为的外星人......他们都是乘坐UFO来地球的,长的嗯哼可能比较有特色。也许长这样害!其实可能也或许不长
- 最近和一程序员合作项目。弄的我头都大了~埋怨我的CSS命名看不懂~得按照他的来。结果我打开他的页面,看了看,从头第一个开始就是content
- 到目前为止,我已经开发了两个HTML编辑器了,一个用在公司的CMS项目,另一个用在这个Blog(TidyEditor,暂时没有单独发布)。下
- python读取和保存图片5种方法对比python中对象之间的赋值是按引用传递的,如果需要拷贝对象,需要用到标准库中的copy模块方法一:利
- 写了个简洁的隔行变色代码,支持三种动作变化颜色<!DOCTYPE html PUBLIC "-//W3C//DTD XHTM
- python 迭代器与生成器,装饰器迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。迭代器有两个基本的方法:iter()
- 基本介绍环境: Python 3.5+, Pytorch 0.4.1/1.0.0安装:pip install pytorch-pretrai
- Python来进行查询和替换一个文本字符串?可以使用sub()方法来进行查询和替换,sub方法的格式为:sub(replacement, s
- 序列化模块import pickle序列化和反序列化把不能直接存储的数据变得可存储,这个过程叫做序列化。把文件中的数据拿出来,回复称原来的数
- 前言大家在使用pymysql的时候,通过fetchall()或fetchone()可以获得查询结果,但这个返回数据是不包含字段信息的(不如p
- python是一种美丽的语言 ,应用范围也很广,有很多的人开始学习python开发,对于初学者,这里有5本经典的书籍,如果你打算用看书来学习
- 前言相信在日常生活中,平常大家聚在一起总会聊聊天,特别是女生(有冒犯到doge)非常喜欢聊星座,这个男生什么星座呀,那个男生什么星座呀…今天