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

[Apollo]

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.

 

[apollo]

if the 'heapq' module supports user-defined comparasion, this problem will
be much easier.


"Apollo" <[email protected]>
??????:[email protected]...

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.

 

[Steven D'Aprano]

(Top posting and incorrect quoting corrected.)

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:
.... 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))
....[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.

 

[bearophileHUGS]

Apollo:

 my question is how to use 'heapq' to extract the biggest item from the heap?  is it possible?

This wrapper allows you to give a key function:
http://code.activestate.com/recipes/502295/

Bye,
bearophile

 

[Paddy3118]

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 heapifying something that will be compared by number, then use the
negative of the number in the object to be heapified. You can then
negate it when popped.

- Paddy.