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
2010-03-23 16:05:39
That's kind of a kludgy solution...
Douglas Mayle
2010-03-23 16:09:47
It's also the standard solution.
Andrew McGregor
2010-03-23 16:30:27
uggh; total kludge. I am surprised `heapq` does not provide a reverse.
shabbychef
2010-04-17 00:33:31
Wow. I'm *amazed* that this is not provided by `heapq`, and that there is no good alternative.
ire_and_curses
2010-06-10 17:46:50
+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
2010-03-23 16:11:19
“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.
ΤΖΩΤΖΙΟΥ
2010-10-17 07:30:16