本文实例讲述了Python实现优先级队列的方法。分享给大家供大家参考,具体如下:
问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素;
解决方案:采用heapq模块实现一个简单的优先级队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
# example.py # # Example of a priority queue 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 ] # Example use 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 ) print ( "Should be bar:" , q.pop()) print ( "Should be spam:" , q.pop()) print ( "Should be foo:" , q.pop()) print ( "Should be grok:" , q.pop()) |
1
2
3
4
5
6
7
8
9
|
Python 3.4 . 0 (v3. 4.0 : 04f714765c13 , Mar 16 2014 , 19 : 24 : 06 ) [MSC v. 1600 32 bit (Intel)] on win32 Type "copyright" , "credits" or "license()" for more information. >>> = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = RESTART = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = >>> Should be bar: Item( 'bar' ) Should be spam: Item( 'spam' ) Should be foo: Item( 'foo' ) Should be grok: Item( 'grok' ) >>> |
可以看出:第一次执行pop()操作时返回的元素具有最高的优先级;对于相同优先级的两个元素(foo和gork)返回的顺序同它们插入到队列时的顺序相同。
在这段代码中,队列以元组(-priority, self._index, item)的形式组成,priority取负值是为了队列按照从高到低的顺序排列,这和堆默认的从小到大的排序相反。
变量index的作用是对相同优先级的元素以适当的顺序排列,特别对同优先级的元素间做比较操作时扮演了重要的角色。
Item实例无法进行次序比较:
1
2
3
4
5
6
7
8
9
|
a = Item( 'foo' ) b = Item( 'bar' ) print ( 'a<b: ' ,a<b) >>> Traceback (most recent call last): File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py" , line 27 , in <module> print ( 'a<b: ' ,a<b) TypeError: unorderable types: Item() < Item() >>> |
如果以元组(priority, item)的形式来表示元素,只要优先级不同,就可进行比较:
1
2
3
4
5
6
7
8
9
10
11
12
|
a = ( 1 ,Item( 'foo' )) b = ( 5 ,Item( 'bar' )) c = ( 1 ,Item( 'gork' )) print ( 'a<b: ' ,a<b) print ( 'a<c: ' ,a<c) >>> a<b: True Traceback (most recent call last): File "D:\4autotests\02script\python-cookbook\python-cookbook-master\src\1\5.implementing_a_priority_queue\example.py" , line 29 , in <module> print ( 'a<c: ' ,a<c) TypeError: unorderable types: Item() < Item() >>> |
引入额外的索引值,以(priority, index, item)的方式建立元组,就可以避免相同优先级无法比较的问题,因为没有哪两个元组会有相同的index值;
1
2
3
4
5
6
7
8
9
|
a = ( 1 , 0 ,Item( 'foo' )) b = ( 5 , 1 ,Item( 'bar' )) c = ( 1 , 2 ,Item( 'gork' )) print ( 'a<b: ' ,a<b) print ( 'a<c: ' ,a<c) >>> a<b: True a<c: True >>> |
如果想将这个队列用于线程间通信,还需要增加适当的锁和信号机制。
(代码摘自《Python Cookbook》)
希望本文所述对大家Python程序设计有所帮助。
原文链接:http://www.cnblogs.com/apple2016/p/5744620.html