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=[]): ...