本节的内容是要实现一个优先级队列,并且当这个队列进行POP操作的时候,总是先弹出优先级最高的元素。今天我们就跟着文档一起学习一下。
文档使用了heapq模块来实现了一个优先级队列,我们由简到繁。来慢慢分析。
这里先定义一个一会要按优先级排序的 Item。然后用它的2个对象进行比较,发现是会报错的。因为不支持比较。
class Item:
def __init__(self,name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
if __name__ == '__main__':
aa = Item('cat')
bb = Item('dog')
print( aa < bb) #TypeError: '<' not supported between instances of 'Item' and 'Item'
我们非要给这个Item对象排序的话,可以用元组。
aa = (5,Item('cat'))
bb = (4,Item('cat'))
print( aa > bb) #输出为True
但是只用元组的第一个元素进行优先级比较的话,只适用于优先级不同的场景,如果优先级。如果优先级一样,则也会抛出 typeerror的异常。
bb = (4,Item('cat'))
cc = (4,Item('fish'))
print(bb < cc) #TypeError: '<' not supported between instances of 'Item' and 'Item'
那为了避免这种场景,我们就需要在元组的第二个位置再引入一个元素inex,且让index的元素始终是不一样的,这样就优先级相同也不会报错,优先级不同index也不会有影响。 !!Python 在做元组比较时候,如果前面的比较已经可以确定结果了, 后面的比较操作就不会发生了
bb = (4,0,Item('cat'))
cc = (4,1,Item('fish'))
print(bb<cc) #True 此时不报错了,因为有了,0,1 index来做比较了
接下来我们看另一个例子,我在这里定义了一个堆,然后通过heapq的push方法往里添加元组元素,然后再输出heap 和pop。 根据print那行可以得知,默认堆是从低优先级到高优先级排序的,pop每次是弹出最左边的元素。因为最左边的是最小的。这就是小顶堆。也就是小的元素在 堆顶,每次把堆顶的弹出去,然后再维持堆的形状。
heap = []
heapq.heappush(heap,(1,'111'))
heapq.heappush(heap,(0,'222'))
heapq.heappush(heap,(3,'333'))
heapq.heappush(heap,(2,'444'))
print(heap) #[(0, '222'), (1, '111'), (3, '333'), (2, '444')]
print(heapq.heappop(heap)[-1]) #222
# print(heapq.heappop(heap)) # [(0, '222')
# print(heapq.heappop(heap)) # (1, '111')
# print(heapq.heappop(heap)) #(2, '444')
# print(heapq.heappop(heap)) #(3, '333')
我这里的需求是想每次pop,弹出最左边的元素,但是需要最左边的元素是最大的。这就需要我们在往里push 的时候,把优先级从高到低插入。也就是先插入优先级高的,在插入优先级低的,最后也就形成了大顶堆。所以这时候pop,弹出的就是最大的元素了。代码如下,只是需要把优先级改成负数即可。
heap = []
heapq.heappush(heap,(-1,'111'))
heapq.heappush(heap,(0,'222'))
heapq.heappush(heap,(-3,'333'))
heapq.heappush(heap,(-2,'444'))
print(heap) # [(-3, '333'), (-2, '444'), (-1, '111'), (0, '222')]
print(heapq.heappop(heap)) #(-3, '333')
print(heapq.heappop(heap)) # (-2, '444')
print(heapq.heappop(heap)) #(-1, '111')
print(heapq.heappop(heap)) # (0, '222')
到这里我们有以下几个知识点
- 元组比较时候,如果优先级相同则会报错,所以需要添加第二元素 index
- 往堆里插入为了让最大堆元素最先弹出,所以优先级要反着来。
- 单独的Item不能比较
啰嗦了这么多,终于到了最后的用一个heapq来实现一个优先级队列,使得可以按照优先级,每次来pop出优先级最高的元素,完整代码如下
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('dog'),1)
q.push(Item('fish'),5)
q.push(Item('cat'),3)
q.push(Item('bird'),1)
print(q.pop()) #Item('fish')
print(q.pop()) #Item('cat')
print(q.pop()) #Item('dog')
print(q.pop()) #Item('bird')