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

[François Pinard]

[Oren Tirosh]

> A sorted list is a much more general-purpose data structure than a priority
> queue and can be used to implement a priority queue.  [...]  The only
> advantage of a heap is O(1) peek which doesn't seem so critical.  [...]
> the internal order of a heap-based priority queue is very non-intuitive and
> quite useless for other purposes while a sorted list is, umm..., sorted!

It surely occurred to many of us to sort a file (or any set of data)
from the most interesting entry to the least interesting entry, look at
the first 5% to 10%, and drop all the rest.

A heap is a good way to retain the first few percents of items, without
going through the lengths of fully sorting all the rest.  By comparison,
it would not be efficient to use `.sort()' then truncate.

Within a simulation, future events are scheduled while current events
are being processed, so we do not have all the events to `.sort()' first.
It is likely that heaps would beat insertion after binary search, given
of course that both are implemented with the same care, speed-wise.

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard