python实现一个优先级队列

107 阅读 0 评论 71 点赞

我是靠谱客的博主刻苦路灯，这篇文章主要介绍python实现一个优先级队列，现在分享给大家，希望可以做个参考。

今天的主题是：怎样实现一个按优先级排序的队列?　并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素，这里需要借助heapq.py中的heapqpush()和heapqpop()方法完成该队列的设计．

１．heapq.py中部分源码显示如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def heappush(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown(heap, 0, len(heap)-1)
def heappop(heap):
"""Pop the smallest item off the heap, maintaining the heap invariant."""
lastelt = heap.pop()
# raises appropriate IndexError if heap is empty
if heap:
returnitem = heap[0]
heap[0] = lastelt
_siftup(heap, 0)
return returnitem
return lastelt

２．借用heapq 模块实现了一个简单的优先级队列:PriorityQueue.py

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)
if __name__ == "__main__":
q = PriorityQueue()
q.push(Item('python'), 1)
q.push(Item('java'), 5)
q.push(Item('swift'), 4)
q.push(Item('c++'), 1)
for i in range(4):
print(q.pop())

3.result如下：

复制代码

1
2
3
4
5
Item('java')
Item('swift')
Item('python')
Item('c++')
Process finished with exit code 0

４．总结：

仔细观察可以发现,第一个 pop() 操作返回优先级最高的元素．另外注意到如果两个有着相同优先级的元素 ( python 和 c++ ),pop 操作按照它们被插入到队列的顺序返回的,且index 变量的作用是保证同等优先级元素的正确排序（some of from Python Cookbook）．