What do I use for a max-heap implementation in Python?

Question

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?

Supereminent

Answer 1

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.

Sheepshank

It's also the standard solution. – Regimentals

uggh; total kludge. I am surprised heapq does not provide a reverse. – Forepeak

Wow. I'm amazed that this is not provided by heapq, and that there is no good alternative. – Hosey

yeah, inverting doesn't help if you don't have int / float's... in fact, there really doesn't need to be any sensible inverse for an order in general (take, for instance, something isomorphic to the natural numbers). – Sloatman

@gatoatigrado: If you have something that doesn't easily map to int/float, you can invert the ordering by wrapping them in a class with an inverted __lt__ operator. – Sheepshank

And what if you have a mix of positive and negative numbers to begin with? Then what? – Randle

@Aerovistae same advice applies: invert the values (i.e. switch the sign) regardless if positive or negative to begin with. – Trochaic

nneonneo's answer to a duplicate question provides a complete example of @DanielStutzbach's alternate solution: a wrapper class that reverses the total ordering of the contained class. – Assemble

Well, this solution looks painstaking at first. But after implementation, it is actually pretty slick, with minimal code changed. – Popple

Poke. See my answer based on yours. – Ellata

Here's an example showing that @DanielStutzbach 's method works gist.github.com/jtara1/574e87ffa1b49ac09a892aad1620f2f7 – Gian

this is ugly, and how do you invert string? – Gauntlett

@Gauntlett your best bet is to import the private maxheap methods from heapq and implement heappush_max() yourself using those methods. Or create your own wrapper class around strings such at heapify() creates a maxheap for your custom string types. – Utile

heapq STILL hasn't added a maxheap? – Tetraspore

Max-heaps may be available by Python 3.13. See this link for details: discuss.python.org/t/make-max-heap-functions-public-in-heapq/… – Crumble

Answer 2

You can use

import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]    
heapq.heapify(listForTree)             # for a min heap
heapq._heapify_max(listForTree)        # for a maxheap!!

If you then want to pop elements, use:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap

Linehan

Looks like there are some undocumented functions for max heap: _heapify_max, _heappushpop_max, _siftdown_max, and _siftup_max. – Carolinian

Wow. I'm amazed that there IS such a built-in solution in heapq. But then it is totally unreasonable that it is NOT even slightly mentioned at all in the official document! WTF! – Fanya

Somehow I can't find this in Python Python 2.7.3. – Arlon

Hi Lijo, looks like _heapify_max not working for dyanamically added/removed elements? See my code from => #33024715, your insights are appreciated. Thanks. :) – Beghtol

Any of the pop/push functions break the max heap structure, so this method is not feasible. – Shelashelagh

DO NOT USE IT. As LinMa and Siddhartha noticed, push/pop breaks the order. – Geanine

You can use it as long as you don't push new elements and use _heappop_maxto pop them – Maciemaciel

Just to state the obvious, _heapify_max etc. are private functions and therefore not part of the module's API. Use at your own risk, both with respect to functionality and forwards compatibility. – Bluebottle

@Maciemaciel ._heappop_max doesn't exist on my Python 2.7.15, only ._heappushpop_max and ._heapify_max for the underscore methods. Looks like the interface changed in Python 3 to include it. – Tracy

The methods beginning with an underscore are private and can be removed without prior notice. Do not use them. – Trimetric

Since they are private and can be removed without prior notice, you can just implement the methods yourself. – Utile

These private methods are built to support heapq.nsmallest and heapq.merge with reverse=True. – Posy

@Shelashelagh just use _heapify_max() after each push/pop then! – Scouring

@Maciemaciel is there inbuilt method to push element into a max-heap. I tried heapq._heappush_max(heap, item) but its not working. – Hipolitohipp

@Hipolitohipp You can look at the available methods here: github.com/python/cpython/blob/3.10/Lib/heapq.py – Maciemaciel

There is some discussion on possibly making this public API in discuss.python.org/t/make-max-heap-functions-public-in-heapq/… – Petronilapetronilla

This should no be used. This is not part of the public API – Sarasvati

Dealing with a negative value is not work for every use case to simulate the maxheap. This approach is better. I don't know why it is private. BTW, It is still working with the new version of python 3.11 for me. For example, how do you solve this problem with a negative values: leetcode.com/problems/last-stone-weight/description – Skiascope

@Skiascope if you haven't seen it, here's a solution that use negation to solve that problem: github.com/neetcode-gh/leetcode/blob/main/python/… – Kinata

Based on the link in @wim's comment (discuss.python.org/t/make-max-heap-functions-public-in-heapq/…), it seems like max-heaps may be available by Python 3.13. – Crumble

Answer 3

The solution is to negate your values when you store them in the heap, or invert your object comparison like so:

import heapq

class MaxHeapObj(object):
  def __init__(self, val): self.val = val
  def __lt__(self, other): return self.val > other.val
  def __eq__(self, other): return self.val == other.val
  def __str__(self): return str(self.val)

Example of a max-heap:

maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val  # fetch max value
x = heapq.heappop(maxh).val  # pop max value

But you have to remember to wrap and unwrap your values, which requires knowing if you are dealing with a min- or max-heap.

MinHeap, MaxHeap classes

Adding classes for MinHeap and MaxHeap objects can simplify your code:

class MinHeap(object):
  def __init__(self): self.h = []
  def heappush(self, x): heapq.heappush(self.h, x)
  def heappop(self): return heapq.heappop(self.h)
  def __getitem__(self, i): return self.h[i]
  def __len__(self): return len(self.h)

class MaxHeap(MinHeap):
  def heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))
  def heappop(self): return heapq.heappop(self.h).val
  def __getitem__(self, i): return self.h[i].val

Example usage:

minh = MinHeap()
maxh = MaxHeap()
# add some values
minh.heappush(12)
maxh.heappush(12)
minh.heappush(4)
maxh.heappush(4)
# fetch "top" values
print(minh[0], maxh[0])  # "4 12"
# fetch and remove "top" values
print(minh.heappop(), maxh.heappop())  # "4 12"

Gelignite

Nice. I've taken this and added an optional list parameter to __init__ in which case I call heapq.heapify and also added a heapreplace method. – Stonefish

Surprised that no one caught this typo: MaxHeapInt --> MaxHeapObj. Otherwise, a very clean solution indeed. – Poverty

Interestingly Fanchen Bao's answer to this question is very similar: #8876206 – Poverty

Is this line needed? def __eq__(self, other): return self.val == other.val. I think it can also work without it. – Married

@Married Yes it is good to have - whether it is needed depends on the heapify implementation and what you want to do with your heap. We only need to define __lt__ and __eq__ to facilitate all comparisons between MaxHeapObj objects (<, <=, ==, >, >=), which may be needed when e.g. searching your heap. – Gelignite

@ChirazBenAbdelkader Fanchen Bao's linked answer is using a tuple with a custom key object as first element, rather than using the custom object to wrap the elements, so slightly different. The tuple method allows passing a lambda which is cool. – Gelignite

Answer 4

The easiest and ideal solution

Multiply the values by -1

There you go. All the highest numbers are now the lowest and vice versa.

Just remember that when you pop an element to multiply it with -1 in order to get the original value again.

Impressment

Great, but most solution supports the classes/other types, and won't change actual data. The open question is if multiplying value by -1 won't change them (extremely precise float). – Phonograph

@AlexBaranowski. That's true, but that has been the response from the maintainer: bugs.python.org/issue27295 – Utile

Well maintainers have their right not to implement some functionality, but this one IMO is actually useful. – Phonograph

This could be a good solution for some coding round. Otherwise changing data within an application doesn't sound that great. – Amie

Answer 5

The easiest way is to convert every element into negative and it will solve your problem.

import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)

The output will look like:

[-20, -1, -10]

Endres

What about if you have zero and need to push it into the maxHeap? Sorry, just stuck on that – Dagall

Answer 6

I also needed to use a max-heap, and I was dealing with integers, so I just wrapped the two methods that I needed from heap as follows:

import heapq


def heappush(heap, item):
    return heapq.heappush(heap, -item)


def heappop(heap):
    return -heapq.heappop(heap)

And then I just replaced my heapq.heappush() and heapq.heappop() calls with heappush() and heappop() respectively.

Banff

Answer 7

I implemented a max-heap version of heapq and submitted it to PyPI. (Very slight change of the heapq module's CPython code.)

heapq_max

Heapq_max (GitHub)

Installation

pip install heapq_max

Usage

tl;dr: The same as the heapq module, except adding ‘_max’ to all functions.

heap_max = []                           # Creates an empty heap
heappush_max(heap_max, item)            # Pushes a new item on the heap
item = heappop_max(heap_max)            # Pops the largest item from the heap
item = heap_max[0]                      # The largest item on the heap without popping it
heapify_max(x)                          # Transforms the list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item)  # Pops and returns the largest item, and
                                        # adds a new item; the heap size is unchanged

Moe

This implementation uses _private functions of heapq.py. Avoid. – Petronilapetronilla

The English on those entries, e.g. on PyPI, could be improved. E.g., all the articles are missing, and it should probably be "max-heap" (not max Heap or maxHeap). – Cimbalom

Answer 8

This is a simple max-heap implementation based on heapq. Though it only works with numeric values.

import heapq
from typing import List


class MaxHeap:
    def __init__(self):
        self.data = []

    def top(self):
        return -self.data[0]

    def push(self, val):
        heapq.heappush(self.data, -val)

    def pop(self):
        return -heapq.heappop(self.data)

Usage:

max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top())  # 5

Sparkman

Nice and simple! – Engagement

Easiest to understand code, that needs no explanation. – Cavafy

This requires that the heap elements support negation, and that's not a given. – Petronilapetronilla

Answer 9

The simplest way:

from heapq import *

h = [5, 7, 9, 1, 3]
h_neg = [-i for i in h]
heapify(h_neg)            # heapify
heappush(h_neg, -2)       # push
print(-heappop(h_neg))    # pop
# 9

Gaea

How and why is it the best way? What makes it better? – Cimbalom

you are using the wellunderstood stdlib, by inverting your values – Monia

Answer 10

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

Jarv

“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. – Cygnet

Answer 11

Extending the int class and overriding __lt__ is one of the ways.

import queue
class MyInt(int):
    def __lt__(self, other):
        return self > other

def main():
    q = queue.PriorityQueue()
    q.put(MyInt(10))
    q.put(MyInt(5))
    q.put(MyInt(1))
    while not q.empty():
        print (q.get())


if __name__ == "__main__":
    main()

Previdi

It's possible, but I feel like it would slow things down a lot and use a lot of extra memory. MyInt can't really be used outside of the heap structure either. But thank you for typing up an example, it's interesting to see. – Carbylamine

Hah! One day after I commented I ran into the situation where I needed to put a custom object into a heap and needed a max heap. I actually re-googled this post and found your answer and based my solution off of it. (Custom object being a Point with x,y coordinate and lt overriding comparing distance from center). Thank you for posting this, I upvoted! – Carbylamine

Answer 12

Allowing you to chose an arbitrary amount of largest or smallest items

import heapq
heap = [23, 7, -4, 18, 23, 42, 37, 2, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapq.heapify(heap)
print(heapq.nlargest(3, heap))  # [42, 42, 37]
print(heapq.nsmallest(3, heap)) # [-4, -4, 2]

Anarchism

An explanation would be in order. – Cimbalom

My answer is longer than the question. What explanation would you like to add? – Anarchism

wikipedia.org/wiki/Min-max_heap and docs.python.org/3.0/library/heapq.html might also be of some help. – Anarchism

This gives the correct result but doesn't actually use a heap to make it efficient. The doc specifies that nlargest and nsmallest sort the list each time. – Actual

You have just dumped an implementation. E.g, why isn't inversion necessary? Why was this set of functions chosen? Why is the set of chosen functions different from other answers? How is it better / different? How does it answer the question? How is "chose an arbitrary amount of largest or smallest items" related to the question ("What should I use for a max-heap implementation in Python?")? - why is that relevant? For example, does that make it better than other answers? Etc. – Cimbalom

From the Help Center: "...always explain why the solution you're presenting is appropriate and how it works". – Cimbalom

Looks like you spent a lot of time on this questions, you've edited several answers, made lots of comments, I see your name come up 17 times with ctrl-f (as of today). Instead of just griping about my input (and other people too) consider adding to my answer next time. It probably would have taken less time to do that and would have benefited everyone. – Anarchism

Answer 13

I have created a heap wrapper that inverts the values to create a max-heap, as well as a wrapper class for a min-heap to make the library more OOP-like. Here is the gist. There are three classes; Heap (abstract class), HeapMin, and HeapMax.

Methods:

isempty() -> bool; obvious
getroot() -> int; returns min/max
push() -> None; equivalent to heapq.heappush
pop() -> int; equivalent to heapq.heappop
view_min()/view_max() -> int; alias for getroot()
pushpop() -> int; equivalent to heapq.pushpop

Addle

Answer 14

To elaborate on Apoorv Patne's answer, here is a fully documented, annotated and tested Python 3 implementation for the general case.

from __future__ import annotations  # To allow "MinHeap.push -> MinHeap:"
from typing import Generic, List, Optional, TypeVar
from heapq import heapify, heappop, heappush, heapreplace


T = TypeVar('T')


class MinHeap(Generic[T]):
    '''
    MinHeap provides a nicer API around heapq's functionality.
    As it is a minimum heap, the first element of the heap is always the
    smallest.
    >>> h = MinHeap([3, 1, 4, 2])
    >>> h[0]
    1
    >>> h.peek()
    1
    >>> h.push(5)  # N.B.: the array isn't always fully sorted.
    [1, 2, 4, 3, 5]
    >>> h.pop()
    1
    >>> h.pop()
    2
    >>> h.pop()
    3
    >>> h.push(3).push(2)
    [2, 3, 4, 5]
    >>> h.replace(1)
    2
    >>> h
    [1, 3, 4, 5]
    '''
    def __init__(self, array: Optional[List[T]] = None):
        if array is None:
            array = []
        heapify(array)
        self.h = array
    def push(self, x: T) -> MinHeap:
        heappush(self.h, x)
        return self  # To allow chaining operations.
    def peek(self) -> T:
        return self.h[0]
    def pop(self) -> T:
        return heappop(self.h)
    def replace(self, x: T) -> T:
        return heapreplace(self.h, x)
    def __getitem__(self, i) -> T:
        return self.h[i]
    def __len__(self) -> int:
        return len(self.h)
    def __str__(self) -> str:
        return str(self.h)
    def __repr__(self) -> str:
        return str(self.h)


class Reverse(Generic[T]):
    '''
    Wrap around the provided object, reversing the comparison operators.
    >>> 1 < 2
    True
    >>> Reverse(1) < Reverse(2)
    False
    >>> Reverse(2) < Reverse(1)
    True
    >>> Reverse(1) <= Reverse(2)
    False
    >>> Reverse(2) <= Reverse(1)
    True
    >>> Reverse(2) <= Reverse(2)
    True
    >>> Reverse(1) == Reverse(1)
    True
    >>> Reverse(2) > Reverse(1)
    False
    >>> Reverse(1) > Reverse(2)
    True
    >>> Reverse(2) >= Reverse(1)
    False
    >>> Reverse(1) >= Reverse(2)
    True
    >>> Reverse(1)
    1
    '''
    def __init__(self, x: T) -> None:
        self.x = x
    def __lt__(self, other: Reverse) -> bool:
        return other.x.__lt__(self.x)
    def __le__(self, other: Reverse) -> bool:
        return other.x.__le__(self.x)
    def __eq__(self, other) -> bool:
        return self.x == other.x
    def __ne__(self, other: Reverse) -> bool:
        return other.x.__ne__(self.x)
    def __ge__(self, other: Reverse) -> bool:
        return other.x.__ge__(self.x)
    def __gt__(self, other: Reverse) -> bool:
        return other.x.__gt__(self.x)
    def __str__(self):
        return str(self.x)
    def __repr__(self):
        return str(self.x)


class MaxHeap(MinHeap):
    '''
    MaxHeap provides an implement of a maximum-heap, as heapq does not provide
    it. As it is a maximum heap, the first element of the heap is always the
    largest. It achieves this by wrapping around elements with Reverse,
    which reverses the comparison operations used by heapq.
    >>> h = MaxHeap([3, 1, 4, 2])
    >>> h[0]
    4
    >>> h.peek()
    4
    >>> h.push(5)  # N.B.: the array isn't always fully sorted.
    [5, 4, 3, 1, 2]
    >>> h.pop()
    5
    >>> h.pop()
    4
    >>> h.pop()
    3
    >>> h.pop()
    2
    >>> h.push(3).push(2).push(4)
    [4, 3, 2, 1]
    >>> h.replace(1)
    4
    >>> h
    [3, 1, 2, 1]
    '''
    def __init__(self, array: Optional[List[T]] = None):
        if array is not None:
            array = [Reverse(x) for x in array]  # Wrap with Reverse.
        super().__init__(array)
    def push(self, x: T) -> MaxHeap:
        super().push(Reverse(x))
        return self
    def peek(self) -> T:
        return super().peek().x
    def pop(self) -> T:
        return super().pop().x
    def replace(self, x: T) -> T:
        return super().replace(Reverse(x)).x


if __name__ == '__main__':
    import doctest
    doctest.testmod()

https://gist.github.com/marccarre/577a55850998da02af3d4b7b98152cf4

Road

Answer 15

The heapq module has everything you need to implement a max-heap. It does only the heappush functionality of a max-heap. I've demonstrated below how to overcome that.

Add this function in the heapq module:

def _heappush_max(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

And at the end, add this:

try:
    from _heapq import _heappush_max
except ImportError:
    pass

Voila! It's done.

PS - to go to heapq function. First write "import heapq" in your editor and then right click 'heapq' and select go to definition.

Substantialism

Re "right click 'heapq' and select go to definition": What editor did you use? – Cimbalom

Answer 16

In case if you would like to get the largest K element using max heap, you can do the following trick:

nums= [3,2,1,5,6,4]
k = 2  #k being the kth largest element you want to get
heapq.heapify(nums) 
temp = heapq.nlargest(k, nums)
return temp[-1]

Ceilometer

Unfortunately, the time complexity for this is O(MlogM) where M = len(nums), which defeats the purpose of heapq. See the implementation and comments for nlargest here -> github.com/python/cpython/blob/… – Sharper

Thank you for your informative comment, will make sure to check the attached link. – Ceilometer

Answer 17

There's a built-in heap in Python, but here is how build it by yourself. The algorithm is working, but about the efficiency I don't know.

class Heap:

    def __init__(self):
        self.heap = []
        self.size = 0

    def add(self, heap):
        self.heap = heap
        self.size = len(self.heap)

    def heappush(self, value):
        self.heap.append(value)
        self.size += 1

    def heapify(self, heap, index=0):

        mid = int(self.size /2)
        """
            If you want to travel great value from the bottom to the top, you need to repeat swapping by the height of the tree.
            I don't know how I can get the height of the tree. That's why I use sezi/2.
            You can find the height by this formula:
            2^(x) = size+1  Why 2^x? Because the tree is growing exponentially
            xln(2) = ln(size+1)
            x = ln(size+1)/ln(2)
        """

        for i in range(mid):
            self.createTee(heap, index)

        return heap

    def createTee(self, heap, shiftindex):

        """
        """
        """

            This 'pos' variable refer to the index of the parent, only parent with children
                    (1)
                (2)      (3)           Here the size of the list is 7/2 = 3
            (4)   (5)  (6)  (7)        The number of parents is 3, but we use {2, 1, 0} in a 'while' loop.
                                       That is why a set 'pos' to -1.

        """
        pos = int(self.size /2) -1
        """
            This if you want to sort this heap list. We should swap the maximum value in the root of the tree with the last
            value in the list and if you want to repeat this until sort all list, you will need to prevent the function from
            change what we already sorted. I should decrease the size of the list. That will heapify on it.

        """

        newsize = self.size - shiftindex
        while pos >= 0:
            left_child = pos * 2 + 1
            right_child = pos * 2 + 2
            # This means that left child is exist
            if left_child < newsize:
                if right_child < newsize:

                    # If the right child exits, we want to check if the left
                    # child > rightchild.
                    #
                    # If the right child doesn't exist, we can check that
                    # we will get error out of range.
                    if heap[pos] < heap[left_child] and heap[left_child]  > heap[right_child]:
                        heap[left_child], heap[pos] = heap[pos], heap[left_child]
                # Here if the right child doesn't exist
                else:
                    if heap[pos] < heap[left_child]:
                        heap[left_child], heap[pos] = heap[pos], heap[left_child]
            # If the right child exists
            if right_child < newsize:
                if heap[pos] < heap[right_child]:
                    heap[right_child], heap[pos] = heap[pos], heap[right_child]
            pos -= 1

        return heap

    def sort(self):
        k = 1
        for i in range(self.size -1, 0, -1):
            """
            Because this is max-heap, we swap root with last element in the list

            """
            self.heap [0], self.heap[i] = self.heap[i], self.heap[0]
            self.heapify(self.heap, k)
            k += 1

        return self.heap


h = Heap()
h.add([5, 7, 0, 8, 9, 10, 20, 30, 50, -1])
h.heappush(-2)
print(" before heapify ")
print(h.heap)
print(" after heapify ")
print(h.heapify(h.heap, 0))
print(" after sort ")
print(h.sort())

Output

Before heapify

[5, 7, 0, 8, 9, 10, 20, 30, 50, -1, -2]

After heapify

[50, 30, 20, 8, 9, 10, 0, 7, 5, -1, -2]

After sort

[-2, -1, 0, 5, 7, 8, 9, 10, 20, 30, 50]

Diella

Answer 18

arr = [3, 4, 5, 1, 2, 3, 0, 7, 8, 90, 67, 31, 2, 5, 567]
# max-heap sort will lead the array to ascending order
def maxheap(arr, p):

    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i + 1)//2 - 1

            while arr[child]> arr[parent] and child != 0:
                arr[child], arr[parent] = arr[parent], arr[child]
                child = parent
                parent = (parent + 1)//2 -1


def heapsort(arr):
    for i in range(len(arr)):
        maxheap(arr, i)
        arr[0], arr[len(arr)-i-1] = arr[len(arr)-i-1], arr[0]

    return arr


print(heapsort(arr))

Try this.

Andrien

Who said anything about sorting? Why is that relevant? Why is it necessary? Where was this copied from? – Cimbalom

Answer 19

I've created a package called heap_class that implements max-heaps, and also wraps the various heap functions into a list-compatible environment.

>>> from heap_class import Heap
>>> h = Heap([3, 1, 9, 20], max=True)
>>> h.pop()
20

>>> h.peek()  # The same as h[0]
9

>>> h.push(17)  # Or h.append(17)
>>> h[0]  # The same as h.peek()
17

>>> h[1]  # Inefficient, but it works
9

Get a min-heap from a max-heap.

>>> y = reversed(h)
>>> y.peek()
1

>>> y  # The representation is inefficient, but correct
Heap([1, 3, 9, 17], max=False)

>>> 9 in y
True

>>> y.raw()  # Underlying heap structure
[1, 3, 17, 9]

As others have mentioned, working with strings and complex objects in a max-heap is rather hard in heapq because of the different forms of negation. It is easy with the heap_class implementation:

>>> h = Heap(('aa', 4), ('aa', 5), ('zz', 2), ('zz', 1), max=True)
>>> h.pop()
('zz', 2)

Custom keys are supported and work with subsequent pushes/appends and pops:

>>> vals = [('Adam', 'Smith'), ('Zeta', 'Jones')]
>>> h = Heap(vals, key=lambda name: name[1])
>>> h.peek()  # Jones comes before Smith
('Zeta', 'Jones')

>>> h.push(('Aaron', 'Allen'))
>>> h.peek()
('Aaron', 'Allen')

(The implementation is built on heapq functions, so it is all in C or with C-wrappers, except heappush and heapreplace on max-heap which is in Python.)

Lubricity

Answer 20

import heapq
customers = []
heapq.heappush(customers, (2, "Harry"))
heapq.heappush(customers, (3, "Charles"))
heapq.heappush(customers, (1, "Riya"))
heapq.heappush(customers, (4, "Stacy"))
while customers:
     print(heapq.heappop(customers)) #for min heap
     # for max heap
     #heapq._heapify_max(customers) 
     #print(heapq._heappop_max(customers)) 

Allograph

Try this and please let me know whether it is working or not – Allograph