Python实现一个优先级队列的方法

站长资源 2024/11/24 佚名

2 0 1

问题

怎样实现一个按优先级排序的队列？并且在这个队列上面每次 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 模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。

以上就是Python实现一个优先级队列的方法的详细内容，更多关于Python实现优先级队列的资料请关注其它相关文章！

Python,队列,Python,优先级队列

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

评论“Python实现一个优先级队列的方法”

暂无评论...

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒经典版》的玩家都可以获得奖励。

更新日志

2024年11月24日

Python实现一个优先级队列的方法

Python如何输出百分比

PyCharm配置anaconda环境的步骤详解

评论“Python实现一个优先级队列的方法”

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

更新日志

友情链接