reversed heapification?

Stefan Behnel stefan.behnel-n05pAM at web.de
Mon Mar 7 15:22:20 CET 2005


Jeff Epler wrote:
> Can you use something like (untested)
>     class ComparisonReverser:
>         def __init__(self, s): self.s = s
>         def __cmp__(self, o): return cmp(o, self.s)
>         def __lt__...  # or whichever operation hashes use
> then use (ComparisonReverser(f(x)), i, x) as the decorated item
> instead of (f(x), i, x)

Thanks!

That *was* untested ;). To avoid infinite recusion (and other bizarre errors), 
you'd have to compare "o.s" and "self.s".

Heapq uses "<=" internally for all comparisons, so it's enough to implement 
the __le__ method:

def __le__(self, other): return other.s <= self.s

I actually looked at the C-implementation of heapq in 2.4 and saw that it even 
provides distinct implementations for min-heaps and max-heaps. It would be 
sooooo convinient if both of them became part of the module...

Stefan



More information about the Python-list mailing list