built-in max heap API in Python

Question

Default heapq is min queue implementation and wondering if there is an option for max queue? Thanks.

I tried the solution using _heapify_max for max heap, but how to handle dynamically push/pop element? It seems _heapify_max could only be used during initialization time.

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":

    print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

Edit, tried _heapify_max seems not working for dynamically push/pop elements. I tried both methods output the same, both output is, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

def heapsort2(iterable):
    h = []
    heapq._heapify_max(h)
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":

    print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
    print heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

Thanks in advance, Lin

Possible duplicate of [What do I use for a max-heap implementation in Python?](http://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python) — Lukas Graf, Oct 08 '15 at 19:21
@LukasGraf, I am not sure if calling function _heapify_max is good, since I see prefix "_", which seems to be an internal function? — Lin Ma, Oct 08 '15 at 19:22
@LukasGraf, the first solution does not fit me well since I need to handle both integers and strings. :) — Lin Ma, Oct 08 '15 at 19:23
Yes, the situation here isn't really satisfactory. Still, the *question* as such is pretty much an exact duplicate. You may however find [this answer](http://stackoverflow.com/a/12682153/1599111) helpful. — Lukas Graf, Oct 08 '15 at 19:28
@LukasGraf, thanks for all the help. I posted my code, and it seems _heapify_max based solution could not be used in cases which we dynamically pop/push elements? Please feel free to correct me if I am wrong. — Lin Ma, Oct 08 '15 at 21:38
@LukasGraf, posted code which shows _heapify_max solution could not be used in cases which we dynamically pop/push elements, your advice is appreciated. Thanks. — Lin Ma, Oct 08 '15 at 22:21
@theJollySin, vote up for your reply. Do you mean `heappop ` or `pop`? If you could post your code snippet, it will be great to reduce confusions. — Lin Ma, Jul 29 '16 at 18:11
_heapify_max will transform your input into a max heap. However, heappop and heappush are still min-heap based. You can check the source code of heapq module here: https://github.com/python/cpython/blob/master/Lib/heapq.py There is actually a _heappop_max function you can import, which should be used in max heap. There is no _heappush_max available. But you can easily modify heappush function to write one. Or check my version here: https://github.com/he-zhe/heapq_max/blob/master/heapq_max/heapq_max.py#L47 — Zhe He, Aug 03 '16 at 00:23
def heapsort2(iterable): h = [] # heapq._heapify_max(h) move this line below the for loop it will work for value in iterable: heapq.heappush(h, value) heapq._heapify_max(h) — Lijo Joseph, Nov 20 '17 at 12:51

U2EF1 · Accepted Answer · 2015-10-11T08:34:02.713

31

In the past I have simply used sortedcontainers's SortedList for this, as:

> a = SortedList()
> a.add(3)
> a.add(2)
> a.add(1)
> a.pop()
3

It's not a heap, but it's fast and works directly as required.

If you absolutely need it to be a heap, you could make a general negation class to hold your items.

class Neg():
    def __init__(self, x):
        self.x = x

    def __cmp__(self, other):
        return -cmp(self.x, other.x)

def maxheappush(heap, item):
    heapq.heappush(heap, Neg(item))

def maxheappop(heap):
    return heapq.heappop(heap).x

But that will be using a little more memory.

edited Oct 11 '15 at 08:34

answered Oct 11 '15 at 07:14

U2EF1

12,907
3
35
37

good catch. Wondering if your solution works for string, besides numeric types? – Lin Ma Oct 11 '15 at 08:19
1

@LinMa That's what the wrapper's for. If you know your data is numeric you can do a little better by just using `-` as in `def maxheappush(heap, item): heapq.heappush(heap, -item)` and `def maxheappop(heap): return -heapq.heappop(heap)`. – U2EF1 Oct 11 '15 at 08:32
Thanks U2EF1, how and when __cmp__ is called and leveraged? – Lin Ma Oct 11 '15 at 21:46
@LinMa All the time? It's a [builtin](https://docs.python.org/2/library/functions.html#cmp) for comparisons. – U2EF1 Oct 11 '15 at 21:48
Thanks U2EF1, sorry I may not make myself understood. I mean does heappush or heappop call __cmp__ underlying -- I ask this since I do not see __cmp__ is called explicitly? If so, more details are appreciated. – Lin Ma Oct 11 '15 at 21:55
1

@LinMa Yes, operations like `a < b` on `Neg` instances will call `__cmp__`. You can add some print statements if you want to see it being called. – U2EF1 Oct 11 '15 at 22:33
How to implement a peek/ get_top function on this max heap? – anveshtummala Jan 21 '18 at 04:34
1

@anveshtummala With indexing, ala `a[-1]`. – U2EF1 Jan 21 '18 at 05:25
1

sorry for necromancing the old thread, but in response to the last comment above, I think it should be `a[0]` to peek the max item (i.e. item at the root of the heap/tree). – Thariq Nugrohotomo Jul 16 '20 at 05:15
The `class Neg` approach is broken on Python 3. Sadly implementing just `__cmp__` only is not sufficient anymore :'( – Thariq Nugrohotomo Jul 16 '20 at 05:26
1

For python3, implementing `__lt__` is enough. – avmohan May 25 '21 at 22:14

Padraic Cunningham · Answer 2 · 2015-10-12T09:50:47.970

There is a _heappop_max function in the latest cpython source that you may find useful:

def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

If you change the heappush logic using heapq._siftdown_max you should get the desired output:

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()  # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


def heapsort2(iterable):
    h = []
    heapq._heapify_max(h)
    for value in iterable:
        _heappush_max(h, value)
    return [_heappop_max(h) for i in range(len(h))]

Output:

In [14]: heapsort2([1,3,6,2,7,9,0,4,5,8])
Out[14]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

In [15]: heapsort2([7, 8, 9, 6, 4, 2, 3, 5, 1, 0])
Out[15]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

In [16]: heapsort2([19,13,15,17,11,10,14,20,18])
Out[16]: [20, 19, 18, 17, 15, 14, 13, 11, 10]

In [17]: heapsort2(["foo","bar","foobar","baz"])
Out[17]: ['foobar', 'foo', 'baz', 'bar']

built-in max heap API in Python

2 Answers2

Linked