Please show all your work with clear justification

Problem (100 points) Design Heapsort Using a Min-Heap The objective of this exercise is to use a Min-Heap to implement Heapsort to sort an array A. a) (2 points) Define what a min-heap is. b) (3 points) Consider the array A Ai] 4. 5 else largest=1 6 ifr A.heap-size and A[r]>Allargest) largest l largest = r 8 if largest i 9 exchange Ali] with Allargest] 10 MAX-HEAPIFY (A, largest) Rewrite Max-Heapify(A.i) into Min-Heapify(A, 1) to help building a min-heap. (5 points) Execute your procedure Min-Heapify(A.I) to the array A . Provide what the array A becomes after the execution of Min-Heapify(A,I) and draw the resulting heap. You must provide the representation as an array and a heap. You may draw by hand the resulting heap, take a picture of your drawing, and insert it in this file. d) e) (10 points) Analyze the time complexity of your Min-Heapify(A.i) procedure f) (10 points) The following is the Build-Max-Heap(A) procedure BUILD-MAX-HEAP (A) l A.heap-size:. .length 2 for i LA.length/2] downto 1 3 MAX-HEAPIFY (A, i) Rewrite Build-Max-Heap(A) into Build-Min-Heap(A) to build a min-heap. (5 points) Execute your procedure Build-Min-Heap(A) to the array A = . Provide what A becomes after the execution of Build-Min-Heap(A) and draw the g) resulting heap. You must provide the representation as an array and a heap You may draw by hand the resulting heap, take a picture of your drawing, and insert it in this file h) (15 points) Analyze the time complexity of your Build-Min-Heap(A) procedure. (25 points) Review in the textbook the proof of correctness of Build-Max-Heap to show/demonstrate that your Build-Min-Heap(A) is correct. (Use the same method/framework used by the author of the textbook) i) i) (10 points) The following is the Heapsort(A) algorithm: HEAPSORT (A) 1 BUILD-MAX-HEAP(A) 2 foriA.length downto 2 3 exchange All] with Al/] 4 4 A.heap-size -A.heap-size -1 5 MAX-HEAPIFY (A, 1) Rewrite Heapsort(A) using the procedures Build-Min-Heap(A) and Min-Heapify(A.i) you designec Your Heapsort(A) algorithm must produce the same result: a sorted array A in increasing order k) (5 points) Analyze the time and space complexity of your Heapsort(A) algorithm