Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm. HeapSort (A) BUILD-MAX-HEAP (A) for i = A.length down to 2 Exchange A[1] with A[i] A.heap_size = A.heap_size -1 MAX-HEAPIFY (A, 1) // Line X For example, an out-of-order array A = [4.1.3.2.16,9,10,14,8.,7] will become [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] after BUILD-MAX-HEAP (A) Then for each iteration of the loop in HeapSort(A), the array A will become [14., 8, 10, 4, 7, 9, 3, 2, 1, 16] [10, 8, 9, 4, 7, 1, 3, 2, 14, 16] [9, 8, 3, 4, 7, 1. 2. 10, 14, 16) [8, 7, 3, 4, 2, 1, 9, 10, 14, 16] [7, 4, 3, 1, 2, 8, 9, 10, 14, 16] [4, 2, 3,1, 7, 8, 9, 10, 14, 16] [3. 2, 1, 4, 7, 8, 9, 10, 14, 16] [2.1, 3, 4,7, 8, 9, 10, 14, 16] [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] Suppose A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. (a) Show how A will change after BUILD-MAX-HEAP (A) (b) Show how A will change for each iteration of the loop in Heap Sort(A) Given an array out of order, HeapSort() sorts it by using a max-heap. Check out the following algorithm. HeapSort (A) BUILD-MAX-HEAP (A) for i = A.length down to 2 Exchange A[1] with A[i] A.heap_size = A.heap_size -1 MAX-HEAPIFY (A, 1) // Line X For example, an out-of-order array A = [4.1.3.2.16,9,10,14,8.,7] will become [16, 14, 10, 8, 7, 9, 3, 2, 4, 11 after BUILD-MAX-HEAP (A) Then for each iteration of the loop in HeapSort(A), the array A will become [14, 8, 10, 4, 7, 9, 3, 2, 1, 16] [10. 8. 9. 4, 7, 1, 3, 2, 14, 16] [9, 8, 3, 4, 7, 1. 2. 10, 14, 16] [8, 7, 3, 4, 2, 1. 9, 10, 14, 16] [7. 4, 3, 1,2, 8, 9, 10, 14, 16] [4. 2, 3, 1,7, 8, 9, 10, 14, 16] [3, 2, 1, 4, 7, 8, 9, 10, 14, 16] [2. 1, 3, 4, 7, 8, 9, 10, 14, 16] [1, 2, 3, 4,7, 8, 9, 10, 14, 16] Suppose A = [5, 3, 17, 10, 84, 19, 6, 22, 9]. (a) Show how A will change after BUILD-MAX-HEAP (A) (b) Show how A will change for each iteration of the loop in Heap Sort(A)