title: How to implement Priority Queues in Python?
body: <p>Sorry for such a silly question but Python docs are confusing...</p>
  <p><strong>Link 1: Queue Implementation</strong>
  <a href="http://docs.python.org/library/queue.html" rel="nofollow noreferrer">http://docs.python.org/library/queue.html</a></p>
  <p>It says that Queue has a class for the priority queue. But I could not find how to implement it.</p>
  <pre><code>class Queue.PriorityQueue(maxsize=0)
  </code></pre>
  <p><strong>Link 2: Heap Implementation</strong>
  <a href="http://docs.python.org/library/heapq.html" rel="nofollow noreferrer">http://docs.python.org/library/heapq.html</a></p>
  <p>Here they say that we can implement priority queues indirectly using heapq</p>
  <pre><code>pq = []                         # list of entries arranged in a heap
  entry_finder = {}               # mapping of tasks to entries
  REMOVED = '&lt;removed-task&gt;'      # placeholder for a removed task
  counter = itertools.count()     # unique sequence count
  
  def add_task(task, priority=0):
      'Add a new task or update the priority of an existing task'
      if task in entry_finder:
          remove_task(task)
      count = next(counter)
      entry = [priority, count, task]
      entry_finder[task] = entry
      heappush(pq, entry)
  
  def remove_task(task):
      'Mark an existing task as REMOVED.  Raise KeyError if not found.'
      entry = entry_finder.pop(task)
      entry[-1] = REMOVED
  
  def pop_task():
      'Remove and return the lowest priority task. Raise KeyError if empty.'
      while pq:
          priority, count, task = heappop(pq)
          if task is not REMOVED:
              del entry_finder[task]
              return task
      raise KeyError('pop from an empty priority queue'
  </code></pre>
  <p>Which is the most efficient priority queue implementation in Python? And how to implement it?</p>