Implement the MinHeap class by completing the provided skeleton code in the file min_heap.py. Once completed, your implementation will include the following methods:add() is_empty() get_min() remove_min() build_heap() size() clear() heapsort()

-------------------------------------------------------------------------------------------------------------------

#min_heap.py

from dynamic_array import * class MinHeapException(Exception): """ Custom exception to be used by MinHeap class DO NOT CHANGE THIS CLASS IN ANY WAY """ pass class MinHeap: def __init__(self, start_heap=None): """ Initialize a new MinHeap DO NOT CHANGE THIS METHOD IN ANY WAY """ self._heap = DynamicArray() # populate MH with initial values (if provided) # before using this feature, implement add() method if start_heap: for node in start_heap: self.add(node) def __str__(self) -> str: """ Return MH content in human-readable form DO NOT CHANGE THIS METHOD IN ANY WAY """ heap_data = [self._heap[i] for i in range(self._heap.length())] return 'HEAP ' + str(heap_data) def add(self, node: object) -> None: """ This method adds a new object to the MinHeap while maintaining heap property. The runtime complexity of this implementation must be O(log N). """ pass def is_empty(self) -> bool: """ This method returns True if the heap is empty; otherwise, it returns False. The runtime complexity of this implementation must be O(1). """ pass def get_min(self) -> object: """ This method returns an object with the minimum key, without removing it from the heap. If the heap is empty, the method raises a MinHeapException. The runtime complexity of this implementation must be O(1). """ pass def remove_min(self) -> object: """ This method returns an object with the minimum key, and removes it from the heap. If the heap is empty, the method raises a MinHeapException. For the downward percolation of the replacement node: if both children of the node have the same value (and are both smaller than the node), swap with the left child. The runtime complexity of this implementation must be O(log N). """ pass def build_heap(self, da: DynamicArray) -> None: """ This method receives a DynamicArray with objects in any order, and builds a proper MinHeap from them. The current content of the MinHeap is overwritten. The runtime complexity of this implementation must be O(N). """ pass def size(self) -> int: """ This method returns the number of items currently stored in the heap. The runtime complexity of this implementation must be O(1). """ pass def clear(self) -> None: """ This method clears the contents of the heap. The runtime complexity of this implementation must be O(1). """ pass def heapsort(da: DynamicArray) -> None: """ Write a function that receives a DynamicArray and sorts its content in non-ascending order, using the Heapsort algorithm. You must sort the array in place, without creating any data structures. This function does not return anything. You may assume that the input array will contain at least one element, and that values stored in the array are all of the same type (either all numbers, or strings, or custom objects, but never a mix of these). You do not need to write checks for these conditions. The runtime complexity of this implementation must be O(N log N). """ pass # It's highly recommended that you implement the following optional # # function for percolating elements down the MinHeap. You can call # # this from inside the MinHeap class. You may edit the function definition. # def _percolate_down(da: DynamicArray, parent: int) -> None: """ TODO: Write your implementation """ pass

---------------------------------------------------------------------------------------------------------------------------

#dynamic_array.py

from static_array import StaticArray class DynamicArrayException(Exception): """ Custom exception class to be used by Dynamic Array DO NOT CHANGE THIS CLASS IN ANY WAY """ pass class DynamicArray: def __init__(self, start_array=None): """ Initialize new dynamic array DO NOT CHANGE THIS METHOD IN ANY WAY """ self._size = 0 self._capacity = 4 self._data = StaticArray(self._capacity) # populate dynamic array with initial values (if provided) # before using this feature, implement append() method if start_array is not None: for value in start_array: self.append(value) def __str__(self) -> str: """ Return content of dynamic array in human-readable form DO NOT CHANGE THIS METHOD IN ANY WAY """ out = "DYN_ARR Size/Cap: " out += str(self._size) + "/" + str(self._capacity) + ' [' out += ', '.join([str(self._data[_]) for _ in range(self._size)]) return out + ']' def __iter__(self): """ Create iterator for loop DO NOT CHANGE THIS METHOD IN ANY WAY """ self._index = 0 return self def __next__(self): """ Obtain next value and advance iterator DO NOT CHANGE THIS METHOD IN ANY WAY """ try: value = self[self._index] except DynamicArrayException: raise StopIteration self._index += 1 return value def get_at_index(self, index: int) -> object: """ Return value from given index position Invalid index raises DynamicArrayException DO NOT CHANGE THIS METHOD IN ANY WAY """ if index < 0 or index >= self._size: raise DynamicArrayException return self._data[index] def set_at_index(self, index: int, value: object) -> None: """ Store value at given index in the array Invalid index raises DynamicArrayException DO NOT CHANGE THIS METHOD IN ANY WAY """ if index < 0 or index >= self._size: raise DynamicArrayException self._data[index] = value def __getitem__(self, index) -> object: """ Same functionality as get_at_index() method above, but called using array[index] syntax DO NOT CHANGE THIS METHOD IN ANY WAY """ return self.get_at_index(index) def __setitem__(self, index, value) -> None: """ Same functionality as set_at_index() method above, but called using array[index] syntax DO NOT CHANGE THIS METHOD IN ANY WAY """ self.set_at_index(index, value) def is_empty(self) -> bool: """ Return True is array is empty / False otherwise DO NOT CHANGE THIS METHOD IN ANY WAY """ return self._size == 0 def length(self) -> int: """ Return number of elements stored in array DO NOT CHANGE THIS METHOD IN ANY WAY """ return self._size def get_capacity(self) -> int: """ Return the capacity of the array DO NOT CHANGE THIS METHOD IN ANY WAY """ return self._capacity def print_da_variables(self) -> None: """ Print information contained in the dynamic array. Used for testing purposes. DO NOT CHANGE THIS METHOD IN ANY WAY """ print(f"Length: {self._size}, Capacity: {self._capacity}, {self._data}") # ----------------------------------------------------------------------- def resize(self, new_capacity: int) -> None: """ Implement """ pass def append(self, value: object) -> None: """ Implement """ pass def insert_at_index(self, index: int, value: object) -> None: """ Implement """ pass def remove_at_index(self, index: int) -> None: """ Implement """ pass def slice(self, start_index: int, size: int) -> "DynamicArray": """ Implement """ pass def merge(self, second_da: "DynamicArray") -> None: """ Implement """ pass def map(self, map_func) -> "DynamicArray": """ Implement """ pass def filter(self, filter_func) -> "DynamicArray": """ Implement """ pass def reduce(self, reduce_func, initializer=None) -> object: """ Implement """ pass def find_mode(arr: DynamicArray) -> (DynamicArray, int): """ Implement """ pass