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