Given an array A[1..7] = (17, 23, 12, 32, 24, 15, 9), run Heapsort (A, 7)...

 

Transcribed Image Text:

Given an array A[1..7] = (17, 23, 12, 32, 24, 15, 9), run Heapsort (A, 7) to sort the array into non-decreasing order. HEAPSORT (A, n) 1 BUILD-MAX-HEAP(A, n) 2 for in downto 2 3 4 5 swap A[1] with A[i] A.heapsize = A.heapsize - 1 MAX-HEAPIFY(A, 1, i - 1) BUILD-MAX-HEAP(A, n) 1 for i= [n/2] downto 1 MAX-HEAPIFY(A, i, n) 2 MAX-HEAPIFY (A, i, n) LEFT (i) r = RIGHT (i) if 1 ≤ n and A[1] > A[i] largest = 1 - else largest = i if r ≤ n and A[r] > A[largest] largest = r if largest i 1 = exchange A[i] with A[largest] MAX-HEAPIFY (A, largest, n) You've already obtained the resultant array after the first line of Heapsort in the previous question. Now please show how the rest of the Heapsort algorithm is performed by listing the updated array or drawing the corresponding binary tree after each iteration of the for loop of Heapsort. Given an array A[1..7] = (17, 23, 12, 32, 24, 15, 9), run Heapsort (A, 7) to sort the array into non-decreasing order. HEAPSORT (A, n) 1 BUILD-MAX-HEAP(A, n) 2 for in downto 2 3 4 5 swap A[1] with A[i] A.heapsize = A.heapsize - 1 MAX-HEAPIFY(A, 1, i - 1) BUILD-MAX-HEAP(A, n) 1 for i= [n/2] downto 1 MAX-HEAPIFY(A, i, n) 2 MAX-HEAPIFY (A, i, n) LEFT (i) r = RIGHT (i) if 1 ≤ n and A[1] > A[i] largest = 1 - else largest = i if r ≤ n and A[r] > A[largest] largest = r if largest i 1 = exchange A[i] with A[largest] MAX-HEAPIFY (A, largest, n) You've already obtained the resultant array after the first line of Heapsort in the previous question. Now please show how the rest of the Heapsort algorithm is performed by listing the updated array or drawing the corresponding binary tree after each iteration of the for loop of Heapsort.