A Generic Priority Queue For Python

Answer :

You can use Queue.PriorityQueue.

Recall that Python isn't strongly typed, so you can save anything you like: just make a tuple of (priority, thing) and you're set.

I ended up implementing a wrapper for heapq, adding a dict for maintaining the queue's elements unique. The result should be quite efficient for all operators:

class PriorityQueueSet(object):      """     Combined priority queue and set data structure.      Acts like a priority queue, except that its items are guaranteed to be     unique. Provides O(1) membership test, O(log N) insertion and O(log N)     removal of the smallest item.      Important: the items of this data structure must be both comparable and     hashable (i.e. must implement __cmp__ and __hash__). This is true of     Python's built-in objects, but you should implement those methods if you     want to use the data structure for custom objects.     """      def __init__(self, items=[]):         """         Create a new PriorityQueueSet.          Arguments:             items (list): An initial item list - it can be unsorted and                 non-unique. The data structure will be created in O(N).         """         self.set = dict((item, True) for item in items)         self.heap = self.set.keys()         heapq.heapify(self.heap)      def has_item(self, item):         """Check if ``item`` exists in the queue."""         return item in self.set      def pop_smallest(self):         """Remove and return the smallest item from the queue."""         smallest = heapq.heappop(self.heap)         del self.set[smallest]         return smallest      def add(self, item):         """Add ``item`` to the queue if doesn't already exist."""         if item not in self.set:             self.set[item] = True             heapq.heappush(self.heap, item) 

When using a priority queue, decrease-key is a must-have operation for many algorithms (Dijkstra's Algorithm, A*, OPTICS), I wonder why Python's built-in priority queue does not support it. None of the other answers supply a solution that supports this functionality.

A priority queue which also supports decrease-key operation is this implementation by Daniel Stutzbach worked perfectly for me with Python 3.5.

from heapdict import heapdict  hd = heapdict() hd["two"] = 2 hd["one"] = 1 obj = hd.popitem() print("object:",obj[0]) print("priority:",obj[1])  # object: one # priority: 1