# Min Heap in Python and its Operations

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.

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