Python实现优先级队列结构的方法详解
作者:mattkang 发布时间:2022-06-15 20:59:33
最简单的实现
一个队列至少满足2个方法,put和get.
借助最小堆来实现.
这里按"值越大优先级越高"的顺序.
#coding=utf-8
from heapq import heappush, heappop
class PriorityQueue:
def __init__(self):
self._queue = []
def put(self, item, priority):
heappush(self._queue, (-priority, item))
def get(self):
return heappop(self._queue)[-1]
q = PriorityQueue()
q.put('world', 1)
q.put('hello', 2)
print q.get()
print q.get()
使用heapq模块来实现
下面的类利用 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.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.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 模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。
猜你喜欢
- 此程序主要是针对某个目录下的全部文件进行筛选,会删除重复的文件。原理很简单,会计算每个文件的哈希,将哈希存入一个字典,文件名对应哈希。imp
- Web抓取Web站点使用HTML描述,这意味着每个web页面是一个结构化的文档。有时从中 获取数据同时保持它的结构是有用的。web站点不总是
- 前言其实Python使用QQ邮箱发送Email代码很简单,短短几行代码就可以实现这个功能。使用到的模块有smtplib和email这个两个模
- 在印刷排版中“point”是一个绝对的单位,它等于 1/72 英寸。可以用尺子丈量的,物理的英寸。但在CSS中pt的含义
- php遍历目录和文件的场景在很多时候都能用到,遍历目录方法的方法有好几种,那么应该使用
- 关于元组,上一讲中涉及到了这个名词。本讲完整地讲述它。先看一个例子:>>>#变量引用str>>> s =
- <%dim total(7,1) total(1,0)="中国经营报"
- 在 Google 搜索结果页面中,将其 Logo 图标右键另存为后可以发现,它并非单纯的
- 代码如下:--相信大家肯定经常会把数据导入到数据库中,但是可能会有些记录行的所有列的数据是null,这为null的数据是我们不需要 --现在
- 1.CNN概述CNN的整体思想,就是对图片进行下采样,让一个函数只学一个图的一部分,这样便得到少但是更有效的特征,最后通过全连接神经网络对结
- 本文实例讲述了python模拟鼠标拖动操作的方法。分享给大家供大家参考。具体如下:pdf中的书签只有页码,准备把现有书签拖到一个目录中,然后
- django接口可以通过localhost或者127.0.0.1进行访问,但无法通过本机ip地址访问1. 修改django项目中的setti
- 代码如下:--新增表字段 ALTER procedure [dbo].[sp_Web_TableFiled_Insert] (
- 我就废话不多说了,大家还是直接看代码吧!### 以下链接里面的codeimport numpy as npfrom keras.callba
- 我就废话不多说了,大家还是直接看代码吧~old_record=numpy.load('exist.npy')temp_rec
- 首先说明,Supervisor 只能安装在 Python 2.x 环境中!但是基本上所有的 Linux 都同时预装了 Python 2.x
- 这篇文章主要介绍了如何获取Python简单for循环索引,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 目录问题思路代码实现测试效果问题一张excel表格,大概1万行,需要录入系统系统每次最多只能录入500行表格数据,一旦超过500行,就会录入
- 本文实例为大家分享了python实现ftp文件传输的具体代码,供大家参考,具体内容如下主要步骤可以分为以下几步:1.读取文件名2.检测文件是
- 本文实例讲述了Python对切片命名清除索引的方法。分享给大家供大家参考,具体如下:问题:如何清理掉到处都是硬编码的切片索引解决方案:对切片