[Python-Dev] Priority queue (binary heap) python code
Kevin O'Connor
kevin@koconnor.net
Mon, 24 Jun 2002 22:59:41 -0400
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. !" |
------------------------------------------------------------------------