[Python-Dev] Priority queue (binary heap) python code

[Kevin O'Connor]

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