3. HEAPSORT (A) 1 BUILD-MAX-HEAP (A) for i= A.length downto 2 exchange A[1] with A[i] A. heap-size = A. heap-size - MAX-HEAPIFY (A,1) (Exercise 6.4-2 in the textbook) Argue the correctness of the Heapsort algorithm above using the following loop invariant: At the start of each iteration of the for loop of lines 25 , the subarray A[1i] is a max-heap containing the i smallest elements of A, and the subarray A[i+1n] contains the n - i largest elements of A, sorted. You may assume that the Build-Max-Heap and MaxHeapify algorithms work correctly. You must make arguments for the Initialization, Maintenance, and Termination of the invariant as part of your answer. 4. (Exercise 6.5-8 in the textbook) The operation Heap-Delete (A,i) deletes the item at index i from heap A, and ensures that A retains max-heap structure. Give a pseudocode implementation of Heap-Delete that runs on O(lgn) time for an n element max-heap. You are free to use calls to any function in Chapter 6 . Then, give a short explanation for why your implementation works correctly (you don't need a proof, but at least discuss how it's able to handle both of the scenarios below without violating the max-heap property), and why it runs in O(lgn) time. This may look similar to Heap-Extract-Max, but make sure your code can handle both of the following scenarios correctly