Python利用heapq实现一个优先级队列的方法_Python

Python利用heapq实现一个优先级队列的方法

2021-05-26 00:16LazyCat_CiCi Python

今天小编就为大家分享一篇Python利用heapq实现一个优先级队列的方法，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧

实现一个优先级队列，每次pop的元素要是优先级高的元素，由于heapq.heapify(list)默认构建一个小顶堆，因此要将priority变为相反数再push，代码如下：

				?

									import heapq

									class priorityqueue(object):

									  """实现一个优先级队列，每次pop优先级最高的元素"""

									  def __init__(self):

									    self._queue = []

									    self._index = 0

									  def push(self,item,priority):

									    heapq.heappush(self._queue,(-priority,self._index,item))#将priority和index结合使用，在priority相同的时候比较index，pop先进入队列的元素

									    self._index += 1

									  def pop(self):

									    return heapq.heappop(self._queue)[-1]

									if __name__ == '__main__':

									  pqueue = priorityqueue()

									  pqueue.push('d',4)

									  pqueue.push('f',3)

									  pqueue.push('a',6)

									  pqueue.push('s',2)

									  print(pqueue.pop())

									  print(pqueue.pop())

									  print(pqueue.pop())