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? — Lukas Graf
– Lukas Graf, Commented Oct 8, 2015 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
– Lin Ma, Commented Oct 8, 2015 at 19:22
@LukasGraf, the first solution does not fit me well since I need to handle both integers and strings. :) — Lin Ma
– Lin Ma, Commented Oct 8, 2015 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 helpful. — Lukas Graf
– Lukas Graf, Commented Oct 8, 2015 at 19:28
_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: 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: github.com/he-zhe/heapq_max/blob/master/heapq_max/… — Zhe He
– Zhe He, Commented Aug 3, 2016 at 0:23

U2EF1 · Accepted Answer · 2015-10-11 08:34:02Z

31

+50

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, 2015 at 8:34

answered Oct 11, 2015 at 7:14

U2EF1

13.4k3 gold badges38 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

U2EF1 Over a year ago

@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 Over a year ago

@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 Over a year ago

@anveshtummala With indexing, ala a[-1].

Thariq Nugrohotomo Over a year ago

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

avmohan Over a year ago

For python3, implementing __lt__ is enough.

|

Padraic Cunningham · Accepted Answer · 2015-10-12 09:50:47Z

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']

Collectives™ on Stack Overflow

built-in max heap API in Python

2 Answers 2

11 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

11 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related