Prashant Sharma — January 19, 2022
Beginner Programming Python

This article was published as a part of the Data Science Blogathon.

Introduction

We will learn in-depth about the min-heap in Python in this tutorial. This is where we will know. What exactly is a heap? What does Python’s min-heap mean? A heap’s time complexity and applications. Finally, we’ll examine the distinction between a min and max heap. Let us begin immediately!

Min heaps are a subclass of heaps. It is possible to classify heaps into two categories: the minimal and maximal heaps, respectively. A data structure known as a heap is referred to as a heap. Heaps, in general, are similar to trees in that they have a large number of nodes. In a heap, the last node might be either empty or full. The parent node and the child node make up a heap. A binary heap is another term for a heap. If you’re using the max heap, the parent node is always bigger than or equal to the child node. It is also important to note that a parent node is always less than or equal to a child node in the min-heap.

 

What does Python’s min-heap mean?

A min-heap is a collection of nodes. It is one of the heap types. There are two sorts of nodes in a min-heap. A heap contains two nodes: a parent node, or root node, and a child node. A parent or root node’s value should always be less than or equal to the value of the child node in the min-heap. When the parent node exceeds the child node, the heap becomes the max heap. Priority is always given to the smallest element in a min-heap. It is arranged in ascending order.

Example of a Min Heap

 

As can be seen, none of the parent nodes exceeds the child node. Thus, this is the ideal illustration of a min-heap. If this criterion is not met, the heap is minimal.

Implementation of min heap using library functions in python

import heapq as heap
l=[ ]
heap.heappush(l,20)
heap.heappush(l,14)
heap.heappush(l,9)
heap.heappush(l,90)
heap.heappush(l,30)
heap.heappush(l,40)
print("The heap is:",l)
print("The parent node is:",heap.heappop(l))
print("The child nodes are:",l)

Explanation: Here, we will generate a minimal pile using the heapq library. Utilizing all procedures to create a minimal heap. It will indicate which node is the parent and which is the child. Additionally, it will provide the heap’s minimal value, determining which node is the parent.

Output:

The  heар  is:  [9,  20,  14,  90,  30,  40] 
The parent node is: 9
The  сhild  nоdes  аre:  [14,  20,  40,  90,  30]

Representation of min heap in python

As is well known, the minimum heap is a binary tree, and an array is always a representation of a min-heap. The root element of the min-heap is array[0].

Parent node representation

array[(i -1) / 2] 

Left child node representation

array[(2 * i) + 1]

Right child node representation

array[(2 * i) + 1]

Which operations are accessible in the minimal heap?

  • getMin()
  • extractMin()
  • insert()

getMin() operation:

  • It is useful to get the parent node of the min heap.
  • The time соmрlexity оf getMin() is О(1) .

extractMin() operation:

  • The minimal element from the min-heap is removed with this operation.
  • The time complexity of the extractMin() method is O(log n).
  • After deleting the parent node, extractMin() keeps the heap property.

insert() operation:

  • This operation is handy for inserting a new node near the heap’s end.
  • If the new child node is smaller than a parent node, we must swap the parent and child nodes.
  • The time complexity to add a new node to the heap is O(log n).

Python implementation of the min-heap without the use of any library functions

import sys
class minheap:
    def __init__(self, size):
        self.storage=[0]*size
        self.size = size
        self.heap_size = 0
        self.Heap = [0]*(self.size + 1)
        self.Heap[0] = sys.maxsize * -1
        self.parent = 1
        self.root=1
    def getParentIndex(self,index):
        return (index-1)//2
    def getLeftChildIndex(self,index):
        return 2*index+1
    def getRightChildIndex(self,index):
        return 2*index+2
    def hasParent(self,index):
        return self.getParentIndex(index)>=0
    def insert(self,index):
        if self.heap_size >= self.size :
            return
        self.heap_size+= 1
        self.Heap[self.heap_size] = index
        heap = self.heap_size
        while self.Heap[heap] < self.Heap[heap//2]:
            self.swap(heap, heap//2)
            heap = heap//2
    def swap(self, left, right):
        self.Heap[left], self.Heap[right] = self.Heap[right], self.Heap[left]
    def root_node(self, i):
        if not (i >= (self.heap_size//2) and i <= self.heap_size):
            if (self.Heap[i] > self.Heap[2 * i]  or  self.Heap[i] > self.Heap[(2 * i) + 1]):
                if self.Heap[2 * i] < self.Heap[(2 * i) + 1]:
                    self.swap(i, 2 * i)
                    self.root_node(2 * i)
                else:
                    self.swap(i, (2 * i) + 1)
                    self.min_heapify((2 * i) + 1)
    def getMin(self):
        min_value = self.Heap[self.root]
        self.Heap[self.root] = self.Heap[self.root]
        self.size-= 1
        self.root_node(self.root)
        return min_value
    def extractMin(self):
        data=self.Heap[1]
        self.Heap[1]=self.Heap[self.size-1]
        self.size-=1
        return data
    def main(self):
       for i in range(1, (self.heap_size//2)+1):
            print("Parent Node:",str(self.Heap[i]),"Left Node:"+str(self.Heap[2 * i]),"Right Node:",str(self.Heap[2 * i + 1]))
minHeap = minheap(11)
minHeap.insert(70)
minHeap.insert(8)
minHeap.insert(80)
minHeap.insert(3)
minHeap.insert(90)
minHeap.insert(30)
minHeap.insert(23)
minHeap.insert(45)
minHeap.insert(100)
print("The Root element is " ,(minHeap.getMin()))
minHeap.main()
print("Remove node ", minHeap.extractMin())
minHeap.main()

Explanation: We are creating a min-heap using python and utilizing all procedures to develop a minimum heap. It will indicate which node is the parent and which is the child. Additionally, it will provide the heap’s minimal value, determining which node is the parent.

Output

The Root element is  3
Раrent  Nоde:  3  Left  Nоde:8  Right  Nоde:  23
Раrent Nоde: 8 Left Nоde:45 Right Nоde: 90
Parent Node: 23 Left Node:80 Right Node: 30 
Раrent  Nоde:  45  Left  Nоde:70  Right  Nоde:  100
Remove node  3
Раrent  Nоde:  100  Left  Nоde:8  Right  Nоde:  23 
Раrent  Nоde:  8  Left  Nоde:45  Right  Nоde:  90
Раrent  Nоde:  23  Left  Nоde:80  Right  Nоde:  30
Раrent  Nоde:  45  Left  Nоde:70  Right  Nоde:  100

Applications of heap

  • Heap data structures are used for a k-way merging.
  • Graph algorithms like prim’s algorithm use the heap data structure.
  • Appropriate for job scheduling algorithms.
  • This is advantageous for order statistics.

Conclusion

We have finally come to the end of this article. We have learned a lot about the min-heap in Python, and we will continue to learn more. Heap is a data structure that may be used in various situations. I hope you have found this information informative and straightforward to comprehend.

I hope you enjoyed reading the post. If you wish to get in touch with me, you may do so via the following channels:
Alternatively, you may drop me an email if you have any further questions.

The media shown in this article is not owned by Analytics Vidhya and are used at the Author’s discretion. 

About the Author

Prashant Sharma

Currently, I Am pursuing my Bachelors of Technology( B.Tech) from Vellore Institute of Technology. I am very enthusiastic about programming and its real applications including software development, machine learning and data science.

Our Top Authors

Download Analytics Vidhya App for the Latest blog/Article

Leave a Reply Your email address will not be published. Required fields are marked *