heapsort$($arr: 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 one or more homogeneous elements

$($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$).$ If the sort uses an

algorithm other than Heapsort, you will not receive any points for this portion of the

assignment, even if your function passes Gradescope.

Example #$1$:

da $=$ DynamicArray$([100,20,6,200,90,150,300])$

print$($f$$Before: $\{$da$\})$

heapsort$($da$)$

print$($f$$After: $\{$da$\})$

Output:

Before: DYN$\_$ARR Size$/$Cap: $7/8[100,20,6,200,90,150,300]$

After: DYN$\_$ARR Size$/$Cap: $7/8[300,200,150,100,90,20,6]$

Example #$2$:

da $=$ DynamicArray$([\text{'}$monkey$\text{'},$ 'zebra', 'elephant', 'horse', 'bear'$])$

print$($f$$Before: $\{$da$\})$

heapsort$($da$)$

print$($f$$After: $\{$da$\})$

Output:

Before: DYN$\_$ARR Size$/$Cap: $5/8[$monkey$,$ zebra, elephant, horse, bear$]$

After: DYN$\_$ARR Size$/$Cap: $5/8[$zebra$,$ monkey, horse, elephant, bear$]$

Can you implement this question?

def heapsort$($da: DynamicArray$)->$ None:

$"""$

TODO: Write this implementation

$"""$

# 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. #