Introduction to Algorithm Third edition

HEAPSORT (A) 1 BUILD-MAX-HEAP(A) 2 for i=A.length downto2 3 exchange A[l] with Ali] 4 5 MAX-HEAPIFY (A, 1) A. heap-size - A.heap-size -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 2-5, the subarray A[1...i] is a max- heap containing the i smallest elements of A, and the subarray Ali+1...n] contains the n i largest elements of A, sorted. You may assume that the Build-Max-Heap and Max-Heapify algorithms work correctly. You must make arguments for the Initialization, Maintenance, and Termination of the invariant as part of your