On Mon, Jun 24, 2002 at 09:00:49PM -0500, Skip Montanaro wrote:
Kevin> I often find myself needing priority queues in python, and I've Kevin> finally broken down and written a simple implementation.
Hmmm... I don't see a priority associated with items when you push them onto the queue in heappush(). This seems somewhat different than my notion of a priority queue.
Hi Skip, I should have included a basic usage in my original email:
t = []; heappush(t, 10); heappush(t, 20); heappush(t, 15); heappush(t, 5) print heappop(t), heappop(t), heappop(t), heappop(t) 20 15 10 5
The binary heap has the property that pushing takes O(log n) time and popping takes O(log n) time. One may push in any order and a pop() always returns the greatest item in the list. I don't explicitly associate a priority with every item in the queue - instead I rely on the user having a __cmp__ operator defined on the items (if the default does not suffice). The same behavior can be obtained using sorted lists:
from bisect import insort t = []; insort(t, 10); insort(t, 20); insort(t, 15); insort(t, 5) print t.pop(), t.pop(), t.pop(), t.pop() 20 15 10 5
But insort takes a lot more overhead on large lists.
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?
Perhaps I am, because I do not see how one would use Queue.Queue efficiently for this task. Cheers, -Kevin -- ------------------------------------------------------------------------ | Kevin O'Connor "BTW, IMHO we need a FAQ for | | kevin@koconnor.net 'IMHO', 'FAQ', 'BTW', etc. !" | ------------------------------------------------------------------------