Prashant Sharma — January 19, 2022

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 if you have any further questions.