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

[François Pinard]

[Matthias Urlichs]

> Oren Tirosh <oren-py-d@hishome.net>:

> >  When I want to sort a list I just use .sort(). I don't care which
> >  algorithm is used.

> The point in this discussion, though, is that frequently you don't need
> a sorted list. You just need a list which yields all elements in order
> when you pop them.  Heaps are a nice low-overhead implementation of that
> idea, and therefore should be in the standard library.

This is especially true when you need only the first few elements from the
sorted set, which is a pretty common case in practice.  A blind sort is
not always the optimal solution, when you want to spare some CPU time.
A caricatural example of abuse would be to implement `max' as `sort'
followed by peeking at the first element of the result.

Heaps are also an efficient enough representation if you insert while
sorting, as it often happens in simulations.  Someone I know studied
this intensely, and came up with better algorithms on average of his
reference benchmark, but with much worse worst cases -- so it depends of
the characteristics of the simulation.  Heaps do quite well on average,
and do acceptably well also in their worst cases.

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