python 实现一个优先级队列

实现一个优先级队列

• 问题

  怎样实现一个按优先级排序的队列？ 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素

• 实现

  import heapq
  
  class PriorityQueue(object):
      def __init__(self):
          self._queue = []
          self._index = 0
         
      def push(self, itme, priority):
     	    heapq.heappush(self._queue, (-priority, self._index, item))
     	    self._index += 1
     	
     	def pop(self):
     	    heapq.heappop(self._queue)[-1]
   
  注：
    由于 push 和 pop 操作时间复杂度为 O(log N)，其中 N 是堆的大小，因此就算是 N 很大的时候它们运行速度也依旧很快；
    优先级为负数的目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。
    index 变量的作用是保证同等优先级元素的正确排序。

  注：heapq 为python处理堆数据结构的一个模块，用法参考：
  [python heapq module] https://forgetst.github.io/2019/09/01/python-module-heapq/

Reference

  https://python3-cookbook.readthedocs.io/zh_CN/latest/index.html