Title: Heap class for heapq module
Type: Stage:
Components: Library (Lib) Versions:
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: loewis, rhettinger, scoder
Priority: normal Keywords: patch

Created on 2005-03-13 10:45 by scoder, last changed 2008-03-24 08:04 by rhettinger. This issue is now closed.

File name Uploaded Description Edit scoder, 2005-03-14 13:14 Version fixing cmp/key interaction
Messages (7)
msg47954 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2005-03-13 10:45
Bug 1158313 (requesting functions for heap iteration)
was rejected, one of the reasons being that iteration
does not fit well with the module design providing
helper functions.

Here is an implementation of a Heap class for that
module that encapsulates a list. It supports iteration
as well as the usual keyword arguments passed to sort()
or sorted(): key, cmp, reversed. It further supports
skipping the heapify step (heapify=True/False) when
constructing the heap as well as copying the list if
unnecessary (copy=True/False). The latter is generally
discouraged and not the default. It is, however, useful
for one-shot sequence generation as in

>>> h = Heap([ random() for i in range(1000) ], copy=False)

A further feature (somewhat obvious for heaps) is that
iteration is not interrupted by items being pushed on
the heap, they are simply integrated.

"heapreplace" is supported by a "pushpop" function as
initially proposed by R. Hettinger. It always returns
the smallest item, also considering the one being pushed.

This implementation is complementary to the existing
functions that work on arbitrary (mutable) sequences.
Both have their use cases and both make sense in the
module. The Heap class has the additional advantage of
encapsulating the list and thus allowing to support
special item comparisons in a consistent way.

There is not yet any documentation or unit tests, but
they should be easy to write once the Heap class is
actually considered for integration.
msg47955 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2005-03-13 11:00
Logged In: YES 

Forgot undecoration in __getitem__ method. Updated patch.
msg47956 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2005-03-14 12:15
Logged In: YES 

The semantics of combining cmp and key are not specified in
the Python documentation and my last implementation differed
from the semantics of sort() and sorted() in that regard.
The new patch fixes this and does some clean up. It also
introduces a method iter_clone() that returns an independent
msg47957 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2005-03-14 12:18
Logged In: YES 

assigned to rhettinger
msg47958 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2005-03-14 13:14
Logged In: YES 

The things that pychecker doesn't tell you ...
msg47959 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2007-03-06 13:38
Can you please provide patches to Doc/lib/libheapq.tex and Lib/test/ Please also put doc strings into the class.

Please drop the type assertions in __init__. I find it quite magical that it will silently turn copy on if the iterator doesn't support len or indexing.

Why is iteration through the heap destructive? No other container has that feature.

Putting the sanity checks into the module isn't necessary - just use the regular test suite for that.

I can't comment further - lack of comments in the patch prevents me from actually understanding it. In the current form, I recommend rejection.

Unassigning Raymond.
msg64396 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-03-24 08:04
Overall, I'm not in favor of the patch or the basic idea.  The heapq 
module is somewhat usable as-is with apps typically inserting tuples 
linking a priority level and a record.  

Also, the attached code is not yet mature, nor does it evidence 
compelling use cases or user demand.  This may make a good ASPN recipe 
but would be premature for inclusion in the standard library.

One quick comment on the API, it would be better to have just a key 
function and to drop the cmp function as Python itself has done 
throughout the language in Py3.0.

Recommend rejecting the feature request, leaving the module as clean as 
possible.  If the code is published separately (perhaps as an ASPN 
recipe or third-party module), it may yet mature and gather a fan club.
Date User Action Args
2008-03-24 08:04:33rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg64396
2005-03-13 10:45:15scodercreate