Also, in case nobody has said so, worst-case performance for insertion into a large heap (log N) is much better than for insertion into a sorted list (N). Of course, in practice, it takes a really large heap to notice these effects.

-Dave

From: "Martin v. Loewis" martin@v.loewis.de

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