USE PYTHON PROGRAMMING!!TO MAKE IT EASIER, THERE'S A CODE TEMPLATE YOU CAN USE!! class MinHeap: def __init__(self): #Filler for zeroth element to have the actual start of indexing to our min heap at arr[1] self.arr = [None] self.size = 0 # Part A. # Fill in the ff. functions such that, given an array implementation arr # of a complete tree and a node at arr[idx], the following functions # correctly return the indices of the left child, right child, and parent # of the given node. Assume that the root node is at arr[1] (NOT arr[0]). def _left_child(self, idx): return __________ # Fill in the blank. def _right_child(self, idx): return __________ # Fill in the blank. def _parent(self, idx): return __________ # Fill in the blank. def _swap_nodes(self, i, j): '''Helper function for swapping two nodes at indices i and j.''' self.arr[i], self.arr[j] = self.arr[j], self.arr[i] def _bubble_down(self, idx): ''' Bubbles down a node at arr[idx] to preserve min-heap properties. Specifically, a node needs to be moved down the heap if its value is greater than either of its children's values. To ensure that the least node is at the top of the heap, the current node is swapped with the lesser of its two children. ''' # Part B. # This is a standard implementation of a bubble down algorithm for min heap. # Modify this accordingly to accomodate Constraint #3 which indicates # that you need to order alphabetically regardless of character case. left_idx = self._left_child(idx) right_idx = self._right_child(idx) if (left_idx > self.size): return elif (right_idx > self.size): left_val = self.arr[left_idx] if (left_val < self.arr[idx]): self._swap_nodes(left_idx, idx) else: left_val = self.arr[left_idx] right_val = self.arr[right_idx] if (left_val < self.arr[idx] and left_val < right_val): self._swap_nodes(left_idx, idx) self._bubble_down(left_idx) elif (right_val < self.arr[idx] and right_val < left_val): self._swap_nodes(right_idx, idx) self._bubble_down(right_idx) def _bubble_up(self, idx): ''' Bubbles up a node at arr[idx] to preserve min-heap properties. Specifically, a node needs to be moved up the heap if its value is less than its parent's. ''' # Part C. # This is a standard implementation of a bubble up algorithm for min heap. # Modify this accordingly to accomodate Constraint #3 which indicates # that you need to order alphabetically regardless of character case. parent_idx = self._parent(idx) parent_val = self.arr[parent_idx] if (idx == 1): return if (self.arr[idx] < parent_val): self._swap_nodes(parent_idx, idx) if (parent_idx > 1): self._bubble_up(parent_idx) # Part C. # Complete the following function to perform the following operations: # - pop the top node from the min-heap # (i.e. remove the node and return its value) # - swap nodes in the heap to preserve the heap's order and shape # - adjust the count for the number of nodes in the heap def extract(self): '''Removes the minimum element from the heap and returns its value.''' # Extract the results by doing something here. Hint: swap nodes and pop the array result = _________ self.size = __________ # No. of nodes after the top node is popped if (__________): # If the heap still contains nodes... # --- Do something here. --- return result # Part D. # Complete the following function to perform the following operations: # - insert a new node (with value val) into the heap # - swap nodes in the heap to preserve the heap's order and shape # - adjust the count for the number of nodes in the heap def insert(self, val): '''Inserts a new value into the heap.''' idx = __________ # Index where the new value should be placed self.arr.insert(idx, val) self.size = __________ # No. of nodes after insertion if (__________): # If the new node is not the root... # --- Do something here. ---# NOTE: The following statements in main check for the correctness of# your implementation. Do not modify anything beyond this point!if __name__ == '__main__': n = int(input()) ls = list() for i in range(n): ls.append(input().rstrip()) myHeap = MinHeap() for x in ls: myHeap.insert(x) while(myHeap.size != 0): print(myHeap.extract()) You are going to create a data structure composed of strings as individual elements. You are required toUSE THE CODE TEMPLATE TO MAKE IT EASIER!!implement a MinHeap class that uses an array representation. This implementation is done such that gettingthe top element always results in alphabetical order.rclass MinHeap:def init_(self):#Filler for zeroth element to have the actual start of indexing to our mnin heap at arr[1]self.arr = [None]A partially implemented data structure is already shown in the sample code below. The comparison ofelements should be done alphabetically.self.size = 0: Part A.Fill in the ff. functions such that, given an array implenentation ar# of a complete tree and a node at arr[idx], the following functions* correctly return the indices of the left child, right child, and parentof the given node. Assume that the root node is at arr[1] (NOT arr(0]).You may refer to this article for a visualization of heaps represented as arrays:https://www.geeksforgeeks.org/array-representation-of-binary-heap/Input Formatdef left child(self, idx):return ---- Fill 1n the blank.def right_child(self, idx):# Fill inThe first line of input contains a single integer, n, the number of lines to follow.return* Fill in the blank.The next n lines of input each contain a string m, to be inserted into the min heap from first (m;) to last (m).def parent (self, idx):return# Fill in the blank.Constraintsdef _swap_nodes(self, i, j):'Helper function for swapping two nodes at indices i and j.'""self.arr[1], self.arr[j] = self.arr[j], self.arr[1]Osns 100def _bubble_down(self, idx):1s len(m) s 10Bubbles down a node at arr[idx] to preserve min-heap properties.All strings are composed of alphabetical characters only. However, they can be lowercase, uppercase, or acombination of both. This should not affect their ordering.Specifically, a node needs to be moved down the heap if its value isgreater than either of its children's values. To ensure that theleast node is at the top of the heap, the current node is swappedOutput Formatwith the lesser of its two children.Your code should produce n lines of output containing the contents of the min heap arranged in alphabeticalorder.* Part B.# This is a standard implementation of a bubble down algorithm for min heap.* Modify this accordingly to accomodate Constraint #3 which indicates* that you need to order alphabetically regardless of character case.Sample Input 0Sample Output 0left_idx = self._left_child(idx)right_idx = self._right_child(idx)7DaleWilliardDarvyif (left_idx > self.size):returnRangelFerdinandMarcusHerlanHerlanFerdinandelif (right_idx > self.size):left_val = self.arr[left_idx]MarcusRangelDarvyDaleWilliardif (left_val < self.arr[idx]):self. swap_nodes (left_idx, idx) # Part D.# Complete the following function to perform the following operations:# - insert a new node (with value val) into the heap# - swap nodes in the heap to preserve the heap's order and shape# - adjust the count for the number of nodes in the heapelse:left_val = self.arr[left_idx]right_val = self.arr[right_idx]if (left_val < self.arr[idx] and left_val < right_val):self. swap_nodes (left_idx, idx)self. bubble_down (left idx)elif (right_val < self.arr(idx] and right val < left_val):self. swap_nodes (right_idx, idx)self. bubbledown (right_idx)def insert(self, val):'''Inserts a new value into the heap.''"# Index where the new value should be placed= xpLself.arr.insert(idx, val)def bubble_up(self, idx):--------Bubbles up a node at arr[idx] to preserve min-heap properties.self.size =# No. of nodes after insertionSpecifically, a node needs to be moved up the heap if its value isless than its parent's.if (--- -): # If the new node is not the root...# --- Do something here. ---* Part C.This is a standard implementation of a bubble up algorithm for min heap.# Modify this accordingly to accomodate Constraint #3 which indicates# that you need to order alphabetically regardless of character case.# NOTE: The following statements in main check for the correctness ofyour implementation. Do not modify anything beyond this point!== '_main_':#3--name_-parent idx = self._parent (idx)parent_val = self.arr[parent_idx]n = int(input ())ls = list()if (idx == 1):returnfor i in range (n):ls.append (input ().rstrip())if (self.arr[idx] < parent_val):self._swap_nodes (parent_idx, idx)myHeap = MinHeap()if (parent_idx > 1):self. bubble_up(parent_idx)for x in ls:myHeap.insert(x)Part C.* Complete the following function to perform the following operations:- pop the top node fron the min-heap(1.e. remove the node and return its value)- swap nodes in the heap to preserve the heap's order and shape- adjust the count for the number of nodes in the heapwhile (myHeap.size != 0):print(myHeap.extract())def extract (self):"Removes the minimum element from the heap and returns its value.'* Extract the results by doing something here. Hint: swap nodes and pop the arrayresult = --------self.size =--------- - No. of nodes after the top node is poppedif (-------): # If the heap still contains nodes...- --- Do something here. ---return result* Part D.Comolete the followins function to perform the folloudng onerations:

PROGRAM INTRODUCTION: Declare the required variables outside all the methods that are going to be…

USE PYTHON PROGRAMMING!! TO MAKE IT EASIER, THERE'S A CODE TEMPLATE YOU CAN USE!! class MinHeap: def __init__(self): #Filler for zeroth element to have the actual start of indexing to our min heap at arr[1] self.arr = [None] self.size = 0 # Part A. # Fill in the ff. functions such that, given an array implementation arr # of a complete tree and a node at arr[idx], the following functions # correctly return the indices of the left child, right child, and parent # of the given node. Assume that the root node is at arr[1] (NOT arr[0]). def _left_child(self, idx): return __________ # Fill in the blank. def _right_child(self, idx): return __________ # Fill in the blank. def _parent(self, idx): return __________ # Fill in the blank. def _swap_nodes(self, i, j): '''Helper function for swapping two nodes at indices i and j.''' self.arr[i], self.arr[j] = self.arr[j], self.arr[i] def _bubble_down(self, idx): ''' Bubbles down a node at arr[idx] to preserve min-heap properties. Specifically, a node needs to be moved down the heap if its value is greater than either of its children's values. To ensure that the least node is at the top of the heap, the current node is swapped with the lesser of its two children. ''' # Part B. # This is a standard implementation of a bubble down algorithm for min heap. # Modify this accordingly to accomodate Constraint #3 which indicates # that you need to order alphabetically regardless of character case. left_idx = self._left_child(idx) right_idx = self._right_child(idx) if (left_idx > self.size): return elif (right_idx > self.size): left_val = self.arr[left_idx] if (left_val < self.arr[idx]): self._swap_nodes(left_idx, idx) else: left_val = self.arr[left_idx] right_val = self.arr[right_idx] if (left_val < self.arr[idx] and left_val < right_val): self._swap_nodes(left_idx, idx) self._bubble_down(left_idx) elif (right_val < self.arr[idx] and right_val < left_val): self._swap_nodes(right_idx, idx) self._bubble_down(right_idx) def _bubble_up(self, idx): ''' Bubbles up a node at arr[idx] to preserve min-heap properties. Specifically, a node needs to be moved up the heap if its value is less than its parent's. ''' # Part C. # This is a standard implementation of a bubble up algorithm for min heap. # Modify this accordingly to accomodate Constraint #3 which indicates # that you need to order alphabetically regardless of character case. parent_idx = self._parent(idx) parent_val = self.arr[parent_idx] if (idx == 1): return if (self.arr[idx] < parent_val): self._swap_nodes(parent_idx, idx) if (parent_idx > 1): self._bubble_up(parent_idx) # Part C. # Complete the following function to perform the following operations: # - pop the top node from the min-heap # (i.e. remove the node and return its value) # - swap nodes in the heap to preserve the heap's order and shape # - adjust the count for the number of nodes in the heap def extract(self): '''Removes the minimum element from the heap and returns its value.''' # Extract the results by doing something here. Hint: swap nodes and pop the array result = _________ self.size = __________ # No. of nodes after the top node is popped if (__________): # If the heap still contains nodes... # --- Do something here. --- return result # Part D. # Complete the following function to perform the following operations: # - insert a new node (with value val) into the heap # - swap nodes in the heap to preserve the heap's order and shape # - adjust the count for the number of nodes in the heap def insert(self, val): '''Inserts a new value into the heap.''' idx = __________ # Index where the new value should be placed self.arr.insert(idx, val) self.size = __________ # No. of nodes after insertion if (__________): # If the new node is not the root... # --- Do something here. --- # NOTE: The following statements in main check for the correctness of # your implementation. Do not modify anything beyond this point! if __name__ == '__main__': n = int(input()) ls = list() for i in range(n): ls.append(input().rstrip()) myHeap = MinHeap() for x in ls: myHeap.insert(x) while(myHeap.size != 0): print(myHeap.extract())