【Cookbook】实现一个优先级队列

dlnb526

问题
怎样实现一个按优先级排序的队列？ 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素

                               
登录/注册后可看大图

解决方案
下面的类利用 heapq 模块实现了一个简单的优先级队列：

1. import heapq
   
2. 
   
3. class PriorityQueue:
   
4.     def __init__(self):
   
5.         self._queue = []
   
6.         self._index = 0
   
7. 
   
8.     def push(self, item, priority):
   
9.         heapq.heappush(self._queue, (-priority, self._index, item))
   
10.         self._index += 1
    
11. 
    
12.     def pop(self):
    
13.         return heapq.heappop(self._queue)[-1]

复制代码

下面是它的使用方式：

1. >>> class Item:
   
2. ...     def __init__(self, name):
   
3. ...         self.name = name
   
4. ...     def __repr__(self):
   
5. ...         return 'Item({!r})'.format(self.name)
   
6. ...
   
7. >>> q = PriorityQueue()
   
8. >>> q.push(Item('foo'), 1)
   
9. >>> q.push(Item('bar'), 5)
   
10. >>> q.push(Item('spam'), 4)
    
11. >>> q.push(Item('grok'), 1)
    
12. >>> q.pop()
    
13. Item('bar')
    
14. >>> q.pop()
    
15. Item('spam')
    
16. >>> q.pop()
    
17. Item('foo')
    
18. >>> q.pop()
    
19. Item('grok')
    
20. >>>

复制代码

仔细观察可以发现，第一个 pop() 操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素（ foo 和 grok ），pop 操作按照它们被插入到队列的顺序返回的。

讨论
这一小节我们主要关注 heapq 模块的使用。 函数 heapq.heappush() 和 heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素， 并且队列 _queue 保证第一个元素拥有最高优先级（ 之前的帖子已经讨论过这个问题）。 heappop() 函数总是返回”最小的”的元素，这就是保证队列pop操作返回正确元素的关键。 另外，由于 push 和 pop 操作时间复杂度为 O(log N)，其中 N 是堆的大小，因此就算是 N 很大的时候它们运行速度也依旧很快。

在上面代码中，队列包含了一个 (-priority, index, item) 的元组。 优先级为负数的目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。

index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量，可以确保元素按照它们插入的顺序排序。 而且， index 变量也在相同优先级元素比较的时候起到重要作用。

为了阐明这些，先假定 Item 实例是不支持排序的：

1. >>> a = Item('foo')
   
2. >>> b = Item('bar')
   
3. >>> a < b
   
4. Traceback (most recent call last):
   
5. File "<stdin>", line 1, in <module>
   
6. TypeError: unorderable types: Item() < Item()
   
7. >>>

复制代码

如果你使用元组 (priority, item) ，只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话，那么比较操作就会跟之前一样出错：

1. >>> a = (1, Item('foo'))
   
2. >>> b = (5, Item('bar'))
   
3. >>> a < b
   
4. True
   
5. >>> c = (1, Item('grok'))
   
6. >>> a < c
   
7. Traceback (most recent call last):
   
8. File "<stdin>", line 1, in <module>
   
9. TypeError: unorderable types: Item() < Item()
   
10. >>>

复制代码

通过引入另外的 index 变量组成三元组 (priority, index, item) ，就能很好的避免上面的错误， 因为不可能有两个元素有相同的 index 值。Python 在做元组比较时候，如果前面的比较已经可以确定结果了， 后面的比较操作就不会发生了：

1. >>> a = (1, 0, Item('foo'))
   
2. >>> b = (5, 1, Item('bar'))
   
3. >>> c = (1, 2, Item('grok'))
   
4. >>> a < b
   
5. True
   
6. >>> a < c
   
7. True
   
8. >>>

复制代码

如果你想在多个线程中使用同一个队列，那么你需要增加适当的锁和信号量机制。

heapq 模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。

1. 摘自《Python Cookbook》第三版
   
2. 翻译项目源地址：https://github.com/yidao620c/python3-cookbook
   
3. Copyright (c) 2014-2018 Xiong Neng and other contributors
   
4. 遵循Apache License 2.0 协议

复制代码

索引贴

暂无，待更新~

由于原项目在线阅读不方便，因此转载给各位鱼油（才不是水！）

Cookbook系列帖子正在不断完善，希望能对已经初步了解python以及算法知识的你有所帮助~

获取更新欢迎关注淘帖https://fishc.com.cn/forum.php?mod=collection&action=view&ctid=1664

喜欢记得评分哦！

X用户

还没学到这个，先马住

扩展阅读

学习学习

iltifa

学习一下

1812099418

0

珂乔乔

来学习一下。

mdphd

还没学到，先收藏

1809228982

感谢分享

永恒的蓝色梦想

为啥这个系列要叫菜谱嘞？

dlnb526

永恒的蓝色梦想 发表于 2020-3-13 18:27
为啥这个系列要叫菜谱嘞？

PythonCookbook是书名~有一系列的编程语言都有广为人知的Cookbook.