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

[Martin v. Loewis]

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

> 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.

And nobody says you should think differently.

> I always find it funny when C++ or Perl programmers refer to an
> associative array as a "hash".

I agree.

> Heaps are a "standard algorithm" only from a CS point of view.  It doesn't
> have much to do with everyday programming.  

This has many different reasons: In the case of Python, the standard
.sort is indeed good for most applications. In general (including
Python), usage of heapsort is rare since it is difficult to implement
and not part of the standard library. Likewise, the naive priority
queue implementation is good in most cases.

If it was more easy to use, I assume it would be used more often.

> 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? ;-)

I don't understand this question: Why do I have to implement anything?
Having heapsort in the library precisely means that I do not have to
write an implementation.

Regards,
Martin