[Patches] [ python-Patches-1162363 ] Heap class for heapq module

[SourceForge.net]

Patches item #1162363, was opened at 2005-03-13 11:45
Message generated for change (Comment added) made by loewis
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1162363&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Library (Lib)
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Stefan Behnel (scoder)
Assigned to: Raymond Hettinger (rhettinger)
Summary: Heap class for heapq module

Initial Comment:
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.


----------------------------------------------------------------------

>Comment By: Martin v. Löwis (loewis)
Date: 2007-03-06 14:38

Message:
Logged In: YES 
user_id=21627
Originator: NO

Can you please provide patches to Doc/lib/libheapq.tex and
Lib/test/test_heapq.py? 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.

----------------------------------------------------------------------

Comment By: Stefan Behnel (scoder)
Date: 2005-03-14 14:14

Message:
Logged In: YES 
user_id=313935

The things that pychecker doesn't tell you ...

----------------------------------------------------------------------

Comment By: Stefan Behnel (scoder)
Date: 2005-03-14 13:18

Message:
Logged In: YES 
user_id=313935

assigned to rhettinger

----------------------------------------------------------------------

Comment By: Stefan Behnel (scoder)
Date: 2005-03-14 13:15

Message:
Logged In: YES 
user_id=313935

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

----------------------------------------------------------------------

Comment By: Stefan Behnel (scoder)
Date: 2005-03-13 12:00

Message:
Logged In: YES 
user_id=313935

Forgot undecoration in __getitem__ method. Updated patch.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1162363&group_id=5470