[Python-Dev] Priority queue (binary heap) python code
Oren Tirosh
oren-py-d@hishome.net
Tue, 25 Jun 2002 04:09:29 -0400
On Tue, Jun 25, 2002 at 09:23:43AM +0200, Martin v. Loewis wrote:
> 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.
When I want to sort a list I just use .sort(). I don't care which algorithm
is used. I don't care whether dictionaries are implemented using hash tables,
some kind of tree structure or magic smoke. I just trust Python to use a
reasonably efficient implementation.
I always find it funny when C++ or Perl programmers refer to an associative
array as a "hash".
> 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.
Heaps are a "standard algorithm" only from a CS point of view. It doesn't
have much to do with everyday programming.
Let's put it this way: If Python has an extension module in the standard
library implementing a sorted list, would you care enough about the
specific binary heap implementation to go and write one or would you just
use what you had in the library for a priority queue? ;-)
Oren