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. !" | ------------------------------------------------------------------------
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4