reversed heapification?
Stefan Behnel
stefan.behnel-n05pAM at web.de
Mon Mar 7 09:22:20 EST 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