Please follow the instructions and justify your answers

The objective of this assignment is to reinforce the understanding of the heap data structure and its application to sorting (Heapsort). 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 . Draw this as a heap and explain whether it is a min-heap or not. You may draw by hand the resulting heap, take a picture of your drawing, and insert it in this file. c) (10 points) The following is the Max-Heapify(A.i) procedure. MAX-HEAPIFY (At) 1 1 = LEFT(i) 2 RIGHTi) 3 ifl A. heap-size and A[/] > A[i] 4 5 else largest=i 6 ifr EA.heap-size and A[r]>largest] largestl 7 8 if largest i 9 exchange Ali] with Alargest] largest = r 10 MAX-HEAPIFY (A. largest) Rewrite Max-Heapify(A.i) into Min-Heapify(A,l) to help building a min-heap. d) (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. e) (10 points) Analyze the time complexity of your Min-Heapify(A.i) procedure. ) (10 points) The following is the Build-Max-Heap(A) procedure BUILD-MAX-HEAP(A) .heq-size-. .length for i A.length/2] downto 1 MAX-HEAP! FY (A,i) Rewrite Build-Max-Heap(A) into Build-Min-Heap(A) to build a min-heap. 8) (5 points) Execute your procedure Build-Min-Heap(A) to the array A 23; 17: 14: 6: 13: 10:1 5: 7: 12>. Provide what A becomes after the execution of Build-Min-Heap(A) 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. 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 A[I] with Ali] A.heap-size = .heap-size-l MAX-HEAPIFY (A, 1) Rewrite Heapsort(A) using the procedures Build-Min-Heap(A) and Min-Heapify (A.i) you designed. Your Heapsort(A) algorithm must produce the same result: a sorted array A in increasing order. k) (5 poings) Analyze thceoplot urHeportAl)algorim