问题

怎样实现一个按优先级排序的队列? 并且在这个队列上面每次 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)) #优先级为负数的目的是使得元素按照优先级从高到低排序
# index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量,可以确保元素按照它们插入的顺序排序
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) print(q.pop())
print(q.pop())
print(q.pop()) # Item('bar')
# Item('spam')
# Item('foo')
# 第一个 pop() 操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素( foo 和 grok ),pop 操作按照它们被插入到队列的顺序返回的。

用heap创建堆

import heapq

nums=[1,2,3,4,5,6,7]
li=[]
for num in nums:
heapq.heappush(li,num)
print(heapq.heappop(li) for _ in range(len(nums))) #<generator object <genexpr> at 0x7fa0ff552938>
print(li) # [1, 2, 3, 4, 5, 6, 7]
05-11 22:13
查看更多