priority queue

[Alex Martelli]

"Nick Perkins" <nperkins7 at home.com> wrote in message
news:TgkT6.142529$eK2.34324960 at news4.rdc1.on.home.com...
> I need a priority queue, but I am not sure what kind I should use.  I will
> be doing insertions that will likely fall somewhere in the middle, and
will
> only be removing from the front of the queue.  I expect insertions to
> out-number removals by about 2 or 3 to one.

That queue is going to grow VERY, VERY big if 2 or 3 things
are inserted into it for each one that is removed...!


> The easy way would be to just have a list, and .sort() it at each
insertion.
> This, i am sure, would not be the fastest way.
>
> I think that a heap would best suit my needs.
> I could code one myself, but it must have been done before.
> I can't find one in the cookbook, or the vaults!

Standard module bisect, particularly with the 2.1 enhancements
(functions insort() & friends), is, I suspect, just what you
want.  To wrap it up as a class:

import bisect
class PriorityQueue:
    def __init__(self, initseq=[]):
        self._seq = list(initseq)
        self._seq.sort()
    def push(self, item):
        bisect.insort(self._seq, item)
    def pop(self):
        return self._seq.pop()
    def __length__(self):
        return len(self._seq)

this uses the end of the self.seq as "front of the queue" --
it will yield the LARGEST current element at each .pop().
Presumably you can arrange your items and their comparison
so that works right for your purposes.  If you'd rather
have an explicit "priority" field accompanying each item:

class AnotherPQ:
    def __init__(self):
        self._seq=[]
    def push(self, item, priority):
        bisect.insort(self._seq, (priority, item))
    def pop(self):
        return self._seq.pop()[1]
    def __length__(self):
        return len(self._seq)

or thereabouts...


For a Heap data structure, see:
http://www.faqts.com/knowledge_base/view.phtml/aid/2820/fid/481



Alex