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

[Martin v. Loewis]

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

> The only advantage of a heap is O(1) peek which doesn't seem so
> critical.  It may also have somewhat better performance by a
> constant factor because it uses an array rather than allocating node
> structures.  But 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!

I think that heaps don't allocate additional memory is a valuable
property, more valuable than the asymptotic complexity (which is also
quite good). If you don't want to build priority queues, you can still
use heaps to sort a list.

IMO, heaps are so standard as an algorithm that they belong into the
Python library, in some form. It is then the user's choice to use that
algorithm or not.

Regards,
Martin