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

**David Abrahams
**
David Abrahams" <david.abrahams@rcn.com

*Wed, 26 Jun 2002 10:14:25 -0400*

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
*