I have to write in Python a build_heap method which receives a dynamic array with objects in any order and builds a proper MinHeap from them. Current content of the MinHeap are lost. Runtime complexity of the implementation must be O(N). I am NOT allowed to use ANY built-in Python data structures and/or their methods. (Assume the other methods in MinHeap are completed and functional)

Example: da = DynamicArray([100, 20, 6, 200, 90, 150, 300]) h = MinHeap(['zebra', 'apple']) print(h) h.build_heap(da) print(h) da.set_at_index(0, 500) print(da) print(h) Output: HEAP ['apple', 'zebra'] HEAP [6, 20, 100, 200, 90, 150, 300] [500, 20, 6, 200, 90, 150, 300] HEAP [6, 20, 100, 200, 90, 150, 300]

# Import pre-written DynamicArray and LinkedList classes from a5_include 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): """ Initializes 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 """ return 'HEAP ' + str(self.heap)

def is_empty(self) -> bool: """ Return True if no elements in the heap, False otherwise DO NOT CHANGE THIS METHOD IN ANY WAY """ return self.heap.length() == 0

def add(self, node: object) -> None: """This method adds a new object to the MinHeap maintaining heap property.""" pass

def get_min(self) -> object: """This method returns an object with a minimum key without removing it from the heap. If the heap is empty, the method raises a MinHeapException.""" return None

def remove_min(self) -> object: """This method returns an object with a minimum key and removes it from the heap. If the heap is empty, the method raises a MinHeapException. Runtime complexity of this implementation is O(logN).""" return None

def build_heap(self, da: DynamicArray) -> None: """ TODO: Write this implementation """ pass

****************** a5_include.py ***************************

class DynamicArray: """ Class implementing a Dynamic Array Supported methods are: append, pop, swap, get_at_index, set_at_index, length

DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """

def __init__(self, arr=None): """ Initialize new dynamic array """ self.data = arr.copy() if arr else []

def __str__(self) -> str: """ Return content of dynamic array in human-readable form """ return str(self.data)

def append(self, value: object) -> None: """ Add new element at the end of the array """ self.data.append(value)

def pop(self) -> object: """ Removes element from end of the array and return it """ return self.data.pop()

def swap(self, i: int, j: int) -> None: """ Swaps values of two elements given their indicies """ self.data[i], self.data[j] = self.data[j], self.data[i]

def get_at_index(self, index: int) -> object: """ Return value of element at a given index """ return self.data[index]

def set_at_index(self, index: int, value: object) -> None: """ Set value of element at a given index """ self.data[index] = value

def length(self): """ Return the length of the DA """ return len(self.data)