How to implement Priority Queues in Python? <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">http://docs.python.org/library/queue.html</a></p> <p>It says thats Queue has a contruct for 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">http://docs.python.org/library/heapq.html</a></p> <p>Here they says 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>