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 模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。

标签:Python,队列
0
投稿

猜你喜欢

  • php字符串截取函数用法分析

    2023-06-28 22:19:26
  • python中的多线程锁lock=threading.Lock()使用方式

    2022-02-12 19:48:39
  • 解决项目pycharm能运行,在终端却无法运行的问题

    2021-11-03 21:05:07
  • SQL Server表中添加新列并添加描述

    2024-01-23 08:10:17
  • MySql存储过程循环的使用分析详解

    2024-01-19 05:13:48
  • ThinkPHP框架实现用户信息查询更新及删除功能示例

    2024-06-07 15:34:11
  • sql中的常用的字符串处理函数大全

    2024-01-19 21:37:41
  • python字典排序实例详解

    2021-10-12 12:12:02
  • django实现web接口 python3模拟Post请求方式

    2023-07-28 15:18:14
  • Tensorflow 自定义loss的情况下初始化部分变量方式

    2023-02-26 22:43:39
  • python禁用键鼠与提权代码实例

    2022-12-11 11:54:59
  • Pandas 实现分组计数且不计重复

    2022-01-30 03:39:56
  • js实现贪吃蛇游戏含注释

    2024-04-19 10:05:44
  • 段正淳的css笔记(7)-表单在各浏览器的表现统一

    2008-01-14 02:47:00
  • python+django加载静态网页模板解析

    2022-06-14 16:58:47
  • python字符串查找函数的用法详解

    2022-12-09 11:32:47
  • 快速升级MySQL系统表

    2009-01-23 12:35:00
  • python+rsync精确同步指定格式文件

    2023-09-18 06:51:26
  • Python创建字典的八种方式

    2021-02-05 20:43:18
  • python3.6使用pymysql连接Mysql数据库

    2024-01-27 13:00:48
  • asp之家 网络编程 m.aspxhome.com