-------------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------------

7) One of the fastest known sorting algorithms is Heapsort. The key phase of this algorithm reorders an array a of integers so that two properties hold for all indices k: This phase of Heapsort is implemented by the method heapify. heapify (a) turns a into a heap in-place public void heapify (int a) for (int root a.length 2 1; root 0; root boolean done false while (2 root 1 a length & & done) 1 nt swap ll (a Swap a L 2 root 1 J Swap 2 root 1; if (2 root 2 a length & & a swap] a C2 root 2 swap 2 root 2 if (Swap root) done true else int temp a root a root. a swap a [swap] temp root swap i a) Show how the application heapify (11,2, 3, 4, 5, 6, 7, 8, 9 is processed. n particular, show the state of a every time it is changed by heapify (7 marks) (3 marks) b) For what data will heapify be especially fast