A generic priority queue for Python

Question

Hello,

I need to use a priority queue in my Python code. Looking around for something efficient, I came upon heapq. It looks good, but seems to be specified only for integers. I suppose it works with any objects that have comparison operators, but it doesn't specify what comparison operators it needs.

Besides, heapq seems to be implemented in Python, so it's not fast.

Are you aware of any fast implementations for priority queues in Python ? Optimally, I'd like the queue to be generic (i.e. work well for any object with a specified comparison operator).

Thanks in advance

Update:

Re comparison in heapq, I can either use a (priority, object) as Charlie Martin suggests, or just implement __cmp__ for my object.

I'm still looking for something faster than heapq.

Answer 1

Um, 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.

Answer 2

Did you look at the "Show Source" link on the heapq page? There's an example a little less than halfway down of using a heap with a list of (int, char) tuples as a priority queue.

Answer 3

I've not used it, but you could try PyHeap. It's written in C so hopefully it is fast enough for you.

Are you positive heapq/PriorityQueue won't be fast enough? It might be worth going with one of them to start, and then profiling to see if it really is your performance bottlneck.

Answer 4

How do you know it's too slow? Have you profiled it yet? Also since 2.4, there's a C implementation of heapq in the standard library which is used.

Answer 5

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.

            items:
                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. The item will be added only
            if it doesn't already exist in the queue.
        """
        if not (item in self.set):
            self.set[item] = True
            heapq.heappush(self.heap, item)