[Python-Dev] Priority queue (binary heap) python code

[Skip Montanaro]

    Kevin> I don't explicitly associate a priority with every item in the
    Kevin> queue - instead I rely on the user having a __cmp__ operator
    Kevin> defined on the items (if the default does not suffice).

That's what I missed.

    >> Seems to me that you could implement the type of priority queue I'm
    >> think of rather easily using a class that wraps a list of Queue.Queue
    >> objects.  Am I missing something obvious?

    Kevin> Perhaps I am, because I do not see how one would use Queue.Queue
    Kevin> efficiently for this task.

I don't know how efficient it would be, but I usually think that most
applications have a small, fixed set of possible priorities, like ("low",
"medium", "high") or ("info", "warning", "error", "fatal").  In this sort of
situation my initial inclination would be to implement a dict of Queue
instances which corresponds to the fixed set of priorities, something like:

    import Queue

    class PriorityQueue:
        def __init__(self, priorities):
            self.queues = {}
            self.marker = Queue.Queue()
            self.priorities = priorities
            for p in priorities:
                self.queues[p] = Queue.Queue()

        def put(self, obj, priority):
            self.queues[priority].put(obj)
            self.marker.put(None)

        def get(self):
            dummy = self.marker.get()
            # at this point we know one of the queues has an entry for us
            for p in self.priorities:
                try:
                    return self.queues[p].get_nowait()
                except Queue.Empty:
                    pass

    if __name__ == "__main__":
        q = PriorityQueue(("low", "medium", "high"))
        q.put(12, "low")
        q.put(13, "high")
        q.put(14, "medium")
        print q.get()
        print q.get()
        print q.get()

Obviously this won't work if your set of priorities isn't fixed at the
outset, but I think it's pretty straightforward, and it should work in
multithreaded applications.  It will also work if for some reason you want
to queue up objects for which __cmp__ doesn't make sense.

Skip