Python Programming question?

plz use template.py below plus some test cases provided

def left(i): return 2 * i + 1 # considering 0 indexed array

def right(i): return 2 * i + 2 # considering 0 indexed array

# Heapify to maintain maximum heap property def max_heapify(arr, cur, heap_size): largest = cur l = left(cur) r = right(cur)

# Find largest key out of the current key at i and its two children # If left child is larger than root if (): # ? largest = l

# If right child is larger than largest so far if (): # ? largest = r

# If largest is not root if largest != cur: # swap values at i and largest # ? # Recursively heapify the affected sub-tree // Bubble Down // maintain heap property max_heapify() # ?

# To start building a max heap, we convert the input array to a heap by maintaining heap property def build_max_heap(arr, heap_size): # We need to maintain heap property by using a for loop and calling max_heapify # For loop starts from middle of array down to 0 because we do not need to care about leaf nodes! # Remember, the assumption is that both left subtrees and right subtrees are already max heaps.

# Index of last non-leaf node middle = int(len(arr) / 2) - 1

# Perform reverse level order traversal from last non-leaf node and max_heapify each node for i in range(middle, -1, -1): max_heapify(arr, i, heap_size)

def heap_sort(arr): # We need to define the current heap size, which is decreasing as we sort curr_heap_size = len(arr)

# Steps to do in each iteration: # 1. Put current max value in the correct position by swapping # 2. Reduce heap size by 1 # 3. Maintain heap property for i in range(len(arr)-1, 0, -1): # swap and put max in correct position # ? # reduce heap size by 1 # ? # maintain heap property max_heapify() # ?

# TESTS print("----------------------------------------------------") arr1 = [3, 1, 6, 5, 2, 4] print("arr1: ", arr1) # Build the heap in arr1 first build_max_heap(arr1, len(arr1)) print("Max heaped arr1: ", arr1) # Sort the heap heap_sort(arr1) print("Sorted arr1: ", arr1)

print("----------------------------------------------------") arr2 = [3, 2, 7, 9, 1, 19, 3, 2, 99, 11] print("arr2: ", arr2) # Build the heap in arr2 first build_max_heap(arr2, len(arr2)) print("Max heaped arr2: ", arr2) # Sort the heap heap_sort(arr2) print("Sorted arr2: ", arr2)

# Have a nice day :)

Inplace Heapsort You are to implement heapsort in an array given as a max-heap. You may use the programming language of your choice. The heapsort algorithm takes a max-heap input array A[1 ... n), where n= A.length. Since the maximum element of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. If we now discard node n from the heap-and we can do so by simply decrementing A heap_size-we observe that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call MaxHeapify (A, 1), which leaves a max-heap in A[1 ... n - 1]. The heapsort algorithm then repeats this process for the max-heap of size n - 1 down to a heap of size 2. Algorithm Heapsort(A): Input: An n-element max-heap in an array, A. Output: Array A sorted. for i = A. length to 2 do swap(A[i],A[1]) A. heap_size = A. heap_size - 1 Max Heapify(A, 1) In order to maintain the max-heap property, we call the procedure Max Heapify. Its inputs are an array A and an index i into the array. When it is called, Max Heapify assumes that the binary trees rooted at 2i and 2i + 1 are max-heaps, but that A[i] might be smaller than its children, thus violating the max-heap property. Max Heapify lets the value at A[i] "bubble down" in the max- heap so that the subtree rooted at index i obeys the max-heap property. Algorithm Max Heapify (A,i): Input: An array, A, and index, i. Output: Maxheap A rooted at i. 12i r+2i +1 if I S A.heap_size and A[l] > A[i] then largest +1 else largest er if larget # i then swap(A[i],A[largest]) Max Heapify(A.largest) end Inplace Heapsort You are to implement heapsort in an array given as a max-heap. You may use the programming language of your choice. The heapsort algorithm takes a max-heap input array A[1 ... n), where n= A.length. Since the maximum element of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. If we now discard node n from the heap-and we can do so by simply decrementing A heap_size-we observe that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call MaxHeapify (A, 1), which leaves a max-heap in A[1 ... n - 1]. The heapsort algorithm then repeats this process for the max-heap of size n - 1 down to a heap of size 2. Algorithm Heapsort(A): Input: An n-element max-heap in an array, A. Output: Array A sorted. for i = A. length to 2 do swap(A[i],A[1]) A. heap_size = A. heap_size - 1 Max Heapify(A, 1) In order to maintain the max-heap property, we call the procedure Max Heapify. Its inputs are an array A and an index i into the array. When it is called, Max Heapify assumes that the binary trees rooted at 2i and 2i + 1 are max-heaps, but that A[i] might be smaller than its children, thus violating the max-heap property. Max Heapify lets the value at A[i] "bubble down" in the max- heap so that the subtree rooted at index i obeys the max-heap property. Algorithm Max Heapify (A,i): Input: An array, A, and index, i. Output: Maxheap A rooted at i. 12i r+2i +1 if I S A.heap_size and A[l] > A[i] then largest +1 else largest er if larget # i then swap(A[i],A[largest]) Max Heapify(A.largest) end