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