Python : Max Heap / Min Heap Using HeapQ

A heap ( min heap or a max heap ) is a data structure that is represented as a binary tree.
Max Heap : Every parent node in the binary tree has a value greater than or equal to its children.
Min Heap : Every parent node in the binary tree has a value less than or equal to its children.

Python3 : Min Heap & Max Heap using heapq and special methods _lt_ or _gt_
- To create a min heap or a max heap, we use the heapq module.
- The heapq module uses an array implementation for representing the heap.
Python_Max_Min_Heap
- The heapq.heapify ( _list ) function transforms the _list of the built-in types into a min-heap in linear time.
- For creating a min heap or a max heap of objects ( user defined types ), _lt_ or _gt_ methods need to be overridden inside the class of object.
       _lt_ is a special ( magic ) method that represents the less than operator.
       _gt_ is a special ( magic ) method that represents the greater than operator.


import heapq

class Mountain :

    def __init__ (self, name, height) :
        self.name = name
        self.height = height

    # Highest height object goes at the top.
    # We override the __lt__ (less than) or __gt__ (greater than) 
    # function to convert the heapq of the objects into a min-heap or a max-heap

    # Create a max-heap by overriding the __gt__ operator.
    # def __gt__ (self, arg_obj) :
    #    return self.freq < arg_obj.freq

    # Get a max-heap by overriding the __lt__ operator.
    def __lt__ (self, arg_obj) :
        return self.height > arg_obj.height

    def __eq__ (self, arg_obj) :
        return self.height == arg_obj.height

class River :

    def __init__ (self, name, length) :
        self.name = name
        self.length = length

    # Create a min-heap by overriding the __lt__ operator.
    def __lt__ (self, arg_obj) :
        return self.length < arg_obj.length

def main() :

    m1 = Mountain("K2", 8611)
    m2 = Mountain("Kangchenjunga", 8586)
    m3 = Mountain("Everest", 8848)
    m4 = Mountain("Annapurna", 8091)

    max_heap_mountains = [m1, m2, m3, m4]

    heapq.heapify(max_heap_mountains)

    print("Max heap using heapq")
    print("Arranging mountain name(s) based on the height (max_heap) of the mountains.")
    print("Mountain with the biggest height comes at the top.\n")
    while max_heap_mountains :
        mount = heapq.heappop(max_heap_mountains)
        print(mount.name + " " + str(mount.height))

    r1 = River("Nile", 4130)
    r2 = River("Amazon", 3976)
    r3 = River("Mississippi", 3917)
    r4 = River("Yangtze", 3902)

    min_heap_rivers = [r1, r2, r3, r4]

    heapq.heapify(min_heap_rivers)

    print("\n\nMin heap using heapq")
    print("Arranging river name(s) based on the lenght (min_heap) of the rivers.")
    print("River with the smallest length comes at the top.\n")
    while min_heap_rivers :
        river = heapq.heappop(min_heap_rivers)
        print(river.name + " " + str(river.length))


    print("\nMin heap using heapq")
    print("Arranging the numbers in increasing order.")
    list_num = [ 3, 2, 5, 1, 10, 7 ]
    heapq.heapify(list_num)

    while list_num :
        print(heapq.heappop(list_num))

if __name__ == "__main__" :
    main()

Output

- Max heap using heapq
Arranging mountain name(s) based on the height (max_heap) of the mountains.
Mountain with the biggest height comes at the top.

Everest 8848
K2 8611
Kangchenjunga 8586
Annapurna 8091

- Min heap using heapq
Arranging river name(s) based on the lenght (min_heap) of the rivers.
River with the smallest length comes at the top.

Yangtze 3902
Mississippi 3917
Amazon 3976
Nile 4130


© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The most disastrous thing that you can ever learn is your first programming language. - Alan Kay"