$\text{'}\text{'}\text{'}$ Familiarize yourself with the minheap implementation $``$MaxHeap$``$ found in the exercise package. The class can be used for simple task prioritization using a queue. The task with the greatest integer has the highest priority. For example, in the task queue $[(1,"$Do homework"$),(3,$ "Eat$),(2,$ "Sleep"$)]$ the task "Eat" has the highest priority. Several of the methods needed by the max heap to work properly have not yet been implemented. Your task is to fix all the methods which contain a row with $``$NotImplementedError$``.\text{'}\text{'}\text{'}$ class MaxHeap: $"""$ A max heap implementation. Elements are stored internally in an array of tuples $($priority$,$ element$),$ where element can be any object and priority is a comparable object. For example for $(5,$ object$3),(23,$ object$2),(1,$ object$7)$ the priority of the objects should be: object$2,$ object$3,$ object$7."""$ def $\_\_$init$\_\_($self$,$ initial$\_$data$=$None$)$: $"""$If initial$\_$data is given, it should be an iterable sequence of tuples $($lists of tuples are fine$)."""$ if initial$\_$data is None: self.clear$()$ else: self.array $=$ list$($initial$\_$data$)$ self.size $=$ len$($self$.$array$)$ for i in range$(($self$.$size $//2)-1,-1,-1)$: self.$\_$heapify$\_$down$($i$)$ def clear$($self$)$: $"""$Delete all elements from the heap and reset its size.""" self.array $=[]$ self.size $=0$ def is$\_$empty$($self$)$: return self.size $==0\text{'}\text{'}\text{'}$def buildheap$($self$)$: $"""$Heapify the existing array.""" # Build the heap by heapifying all internal nodes, # starting from the last internal node up to the root for i in range$(($self$.$size $//2)-1,-1,-1)$: self.$\_$heapify$\_$down$($i$)\text{'}\text{'}\text{'}$ def $\_$swap$($self$,$ i$,$ j$)$: $"""$Swaps in$-$place the priority$-$object pairs at indexes i and j$."""$ if i $!=$ j: self.array$[$j$],$ self.array$[$i$]=$ self.array$[$i$],$ self.array$[$j$]$ def $\_$heapify$\_$up$($self$,$ i$)$: $"""$Restore heap property from the element at i to the root.""" while i $>0$: # Select the parent of i parent$\_$index $=($i $-1)//2$ # If the parent has a lower priority than i$,$ swap parent with i if self.$\_$higher$\_$priority$($i$,$ parent$\_$index$)$: self.$\_$swap$($i$,$ parent$\_$index$)$ # Heapify the parent i $=$ parent$\_$index def $\_$left$\_$child$($self$,$ i$)$: $"""$Return the index of the left child of i$.$ Return $-1$ if i has no left child. Raise an IndexError if the index i is invalid.""" if not $0<=$ i $<$ self.size: raise IndexError$("$A node which does not exist cannot have a left child"$)$ return i$*2+1$ if i $<$ self.size$//2$ else $-1$ def $\_$right$\_$child$($self$,$ i$)$: $"""$Return the index of the right child of i$.$ Return $-1$ if i has no right child. Raise an IndexError if the index i is invalid.""" if not $0<=$ i $<$ self.size: raise IndexError$("$A node which does not exist cannot have a right child"$)$ return i$*2+2$ if i $<($self$.$size$-1)//2$ else $-1$ def $\_$is$\_$leaf$($self$,$ i$)$: $"""$Return False if the node at i has one or more children, else True. Raise an IndexError if the index i is invalid.""" if not $0<=$ i $<$ self.size: raise IndexError$("$A node which does not exist cannot be a leaf"$)$ return $-1==$ self.$\_$left$\_$child$($i$)==$ self.$\_$right$\_$child$($i$)$ def $\_$max$\_$child$($self$,$ i$)$: $"""$Return the index of the child with higher priority of the element at index i$.$ Raise an IndexError if the node at index i is a leaf.""" # Get indexes for the left and right child i$\_$left $=$ self.$\_$left$\_$child$($i$)$ i$\_$right $=$ self.$\_$right$\_$child$($i$)$ if $-1==$ i$\_$left $==$ i$\_$right: # Node i is a leaf raise IndexError$("$The node at index i has no children."$)$ if $-1==$ i$\_$right: # Node i has only a left child return i$\_$left # Node i has two children # Compare the elements and return the index with the higher priority return i$\_$left if self.$\_$higher$\_$priority$($i$\_$left, i$\_$right$)$ else i$\_$right Implement the methods below def $\_$higher$\_$priority$($self$,$ i$,$ j$)$: $"""$Return True if element at index i has a higher priority than the element at index j$,$ else False.""" raise NotImplementedError$("$MaxHeap$.\_$higher$\_$priority not yet implemented."$)$ def insert$($self$,$ pair$)$: $"""$Insert a new $($priority$,$ object$)$ pair into the heap and heapify the heap.""" raise NotImplementedError$("$MaxHeap$.$insert not yet implemented."$)$ def top$($self$)$: $"""$Return the object at the top of the heap or None if heap is empty. $"""$ if self.is$\_$empty$()$: return None raise NotImplementedError$("$MaxHeap$.$top not yet implemented."$)$ def $\_$heapify$\_$down$($self$,$ i$)$: $"""$Restore heap property from the element at i to the last leaf.""" while $0<=$ i $<$ self.size and not self.$\_$is$\_$leaf$($i$)$: raise NotImplementedError$("$MaxHeap$.\_$heapify$\_$down not yet implemented."$)$ def pop$($self$)$: $"""$Remove the pair at the top of the heap and return the removed object. Raises a RuntimeError if the heap is empty.""" # Raise error if the heap is empty if self.is$\_$empty$()$: raise RuntimeError$("$Cannot pop from an empty heap."$)$ raise NotImplementedError$("$MaxHeap$.$pop not yet implemented."$)$