Implement the HeapSort algorithm based on the heap in the skeleton of the class MaxHeap. The heap must be created

using bottom$-$up construction approach $($as described in lecture and exercise$)$ and in$-$place $($without using an additional data

structure$).$ Make sure to use the slightly different template of MaxHeap compared to assignment $5.$

The following methods shall be implemented:

class MaxHeap:

def $\_\_$init$\_\_($self$,$ list$)$:

# Creates a bottom$-$up maxheap in$-$place from the input list of numbers.

def contains$($self$,$ val$)$:

# Tests if an item $($val$)$ is contained in the heap. Do not search the array sequentially, but use the heap properties.

def sort$($self$)$:

# This method sorts the numbers in$-$place using the maxheap data structure in ascending order. a$)$ The MaxHeap$()$ constructor should create a valid maxheap using in$-$place bottom$-$up construction.

b$)$ The method contains$()$ should return true, if the element val is found in the heap $($duplicates allowed$).$ Use the properties

of the maxheap for efficient implementation and do not search the array sequentially!

c$)$ The sort method should implement the HeapSort algorithm in ascending order, using the created maxheap by repeated

removal of the top element in$-$place. Don$$t use intermediate data structures!

You can use private $($help$)$ methods for your implementation. And this is the skeleton: class MaxHeap:

def $\_\_$init$\_\_($self$,$ input$\_$array$)$:

$"""$

@param input$\_$array from which the heap should be created

@raises ValueError if list is None.

Creates a bottom$-$up max heap in place.

$"""$

self.heap $=$ None

self.size $=0$

# TODO

def get$\_$heap$($self$)$:

# helper function for testing, do not change

return self.heap

def get$\_$size$($self$)$:

$"""$

@return size of the max heap

$"""$

return self.size

def contains$($self$,$ val$)$:

$"""$

@param val to check if it is contained in the max heap

@return True if val is contained in the heap else False

@raises ValueError if val is None.

Tests if an item $($val$)$ is contained in the heap. Does not search the entire array sequentially, but uses the

properties of a heap.

$"""$

# TODO

def sort$($self$)$:

$"""$

This method sorts $($ascending$)$ the list in$-$place using HeapSort, e$.$g$.[1,3,5,7,8,9]$

$"""$

# TODO

def remove$\_$max$($self$)$:

$"""$

Removes and returns the maximum element of the heap

@return maximum element of the heap or None if heap is empty

$"""$

# TODO