A generic priority queue for Python

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.

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 heapdicthd = heapdict()hd["two"] = 2hd["one"] = 1obj = hd.popitem()print("object:",obj[0])print("priority:",obj[1])# object: one# priority: 1

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)