views:

157

answers:

2

Python includes the heapq module for min-heaps, but I need a max heap. What should I use for a max-heap implementation in Python?

+2  A: 

The easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.

Daniel Stutzbach
That's kind of a kludgy solution...
Douglas Mayle
It's also the standard solution.
Andrew McGregor
uggh; total kludge. I am surprised `heapq` does not provide a reverse.
shabbychef
Wow. I'm *amazed* that this is not provided by `heapq`, and that there is no good alternative.
ire_and_curses
+1  A: 

If you are inserting keys that are comparable but not int-like, you could potentially override the comparison operators on them (i.e. <= become > and > becomes <=). Otherwise, you can override heapq._siftup in the heapq module (it's all just Python code, in the end).

rlotun
“it's all just Python code”: it depends on your Python version and installation. For example, my installed heapq.py has some code after line 309 (`# If available, use C implementation`) that does exactly what the comment describes.
ΤΖΩΤΖΙΟΥ