Heap class for heapq module

Stefan Behnel stefan.behnel-n05pAM at web.de
Thu Mar 24 08:25:34 CET 2005


Hi!

I filed a patch for a Heap class to be integrated into the heapq module (in 
addition the the currently available functions). The main features are support 
for iteration and for the standard keyword arguments of sort() and sorted(): 
key, cmp, reverse.

http://sourceforge.net/tracker/index.php?func=detail&aid=1162363&group_id=5470&atid=305470

I wrote it because I believe that it makes the API of that module much simpler 
for beginners and more consistent for general purpose use. Currently, it has a 
set of special purpose list functions that must be used in the right way to 
achieve what is needed. The main problems with these functions are:

1) They don't support heap iteration. This is contrary to the obvious paradigm 
shift Python did in the last years. Iteration is considered difficult to 
integrate into the current module as the list that the functions operate on is 
open to modification between heapq calls. A Heap class eliminates this 
problem. It can provide iteration in a consistent way, both for destructive 
iteration as for clone iteration.

2) They don't support sort arguments. They only support min heaps. Usage as 
max heaps needs special treatment of the list items, such as a wrapper class. 
I suspect such a class to be part of every Python programmer's personal tool 
box, which already makes a good case for better support in the stdlib. Also, 
beginners often do not have such a wrapper class and have to figure out how to 
write it or search for it (and must know what they have to search for). Again, 
a Heap class can easily support the standard keyword arguments as it wraps the 
heap list.

I hope for integration of the Heap class in the stdlib heap module, but I'd 
also like to hear a fruitful discussion on this list to get the patch ready 
for integration. I know, it currently misses documentation and tests, but I'm 
ready to add them once the patch is actually considered for integration.

Stefan



More information about the Python-list mailing list