Algotree > Algorithms > Heap Data Structure > Python : Max Heap / Min Heap Using HeapQ

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

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