how to use "heapq" module as a max-heap?

[Steven D'Aprano]

(Top posting and incorrect quoting corrected.)

On Sun, 29 Mar 2009 16:48:53 +0800, apollo wrote:
 
> > as we all known, in the standard module 'heapq',  we can easily get
> > the smallest item from the heap. i.e. it's an implementation of 
> > min-heap.
> > 
> > my question is how to use 'heapq' to extract the biggest item from the
> > heap? is it possible?
> > 
> > thanks  in advance.:)
>
> if the 'heapq' module supports user-defined comparasion, this problem
> will be much easier.



It certain does. Here's one way of turning the min-heap into a fake max-
heap:

>>> class Backwards(float):
...     def __lt__(self, other):
...             return not float.__le__(self, other)
...     def __le__(self, other):
...             return not float.__lt__(self, other)
...     def __gt__(self, other):
...             return not float.__ge__(self, other)
...     def __ge__(self, other):
...             return not float.__gt__(self, other)
...
>>> x, y = Backwards(27), Backwards(1270)
>>> x > y
True
>>> y < x
True
>>> heap = []
>>> for x in xrange(20):
...     heapq.heappush(heap, Backwards(x))
...
>>> heapq.heappop(heap)
19.0
>>> heapq.heappop(heap)
18.0
>>> heap
[17.0, 16.0, 13.0, 15.0, 8.0, 10.0, 12.0, 9.0, 14.0, 2.0, 7.0, 1.0, 5.0, 
4.0, 11.0, 0.0, 6.0, 3.0]

The problem with this approach is that when you pop the "largest" item, 
and compare it to something else, it will compare *smaller* because of 
the custom comparisons, so now you have to remove the custom comparisons 
to revert to the standard behaviour. The book-keeping for this could be 
awful.


However, another approach is to use the nlargest function:


>>> heap = []
>>> for i in (5, 6, 7, 0, 1, 10, 2, 4, 3, 9, 8):
...     heapq.heappush(heap, i)
...
>>> heap
[0, 1, 2, 3, 5, 10, 7, 6, 4, 9, 8]
>>> heapq.nlargest(1, heap)
[10]


The problem with this is that the value is not popped off the heap. Also, 
I'm not sure how efficient nlargest is.



-- 
Steven