使用内置模块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)) #将priority添加负号是为了让队列能够按元素的优先级从高到低排列
#该队列以(-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)
q = PriorityQueue()
q.push(Item("AAA"),1)
q.push(Item("BBB"),4)
q.push(Item("CCC"),5)
q.push(Item("DDD"),1)
print(q.pop())
print(q.pop())
print(q.pop())
输出结果：
Item('CCC')
Item('BBB')
Item('AAA')
分割线-----------------------------------------------------------------------------------
如果以元组(priority,item)形式存储元素，当两个元素的优先级相同时会失败。所以引入index：(priority,index,item)
还是上面的源代码，将输出及压入数据部分更改：
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)
# a = Item("AAA")
# b = Item("BBB")
# print(a<b) error
a = (1,Item("AAA"))
b = (4,Item("BBB"))
print(a<b)#True
c = (1,Item("CCC"))
# print(a<c)#error
a = (1,0,Item("AAA"))
b = (4,1,Item("BBB"))
c = (1,2,Item("CCC"))
print(a<b)#True
print(a<c)#True
