Python’s Pythonic implementation of a max heap API

What is the recommended approach for creating a max heap of strings?
Inquiry:
By default, heapq implements a min queue, but I am curious if there is a possibility of having a max queue.

Question:

Is it possible to change the default heapq implementation from min queue to max queue? Thank you.

I experimented with the _heapify_max method to create a max heap. However, I’m unsure how to manage dynamically adding and removing elements. It appears that _heapify_max can only be used during the initialization process.

import heapq
def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(****(h))]
if __name__ == "__main__":
    print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

I attempted using _heapify_max to handle dynamically pushing and popping elements, but it did not seem to work. I tried both methods and obtained the same output, [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(****(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(****(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


Solution 1:

Previously, I utilized sortedcontainers’s
SortedList
for such purposes.

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

Although it may not be a pile, it operates swiftly and functions precisely as needed.

If a heap is necessary, you have the option to create a general negation class to contain your items.

class Neg():
    def __init__(self, x):
        self.****
    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

However, this would result in a slight increase in memory usage.


Solution 2:


The latest cpython source includes a useful function called _heappop_max that you might find beneficial.

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

By modifying the logic specified in
heappush
with the use of
heapq._siftdown_max
, you can achieve the expected result.

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, ****(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(****(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, **** [15]: heapsort2([7, 8, 9, 6, 4, 2, 3, 5, 1, 0])
Out[15]: [9, 8, 7, 6, 5, 4, 3, 2, **** [16]: heapsort2([19,13,15,17,11,10,14,20,18])
Out[16]: [20, 19, 18, 17, 15, 14, 13, 11, **** [17]: heapsort2(["foo","bar","foobar","baz"])
Out[17]: ['foobar', 'foo', 'baz', 'bar']

Frequently Asked Questions