Question

• Apply the MAX-HEAPIFY algorithm to the following array A on node i = 2 and give the resulting array. | i Ali | 1 | 2 | 3 | 4 | 5 6 | 7 | 8 | 9 | 10 81 19 76 62 54 63 66 38 43 22 Answer: 1 2 3 4 5 6 7 8 9 10 Ai

Answer 1

Output: array[] = {81, 62, 76, 43, 54, 63, 66, 38, 19, 22}

Since left child of ith node is 2*i and right child is 2*i+1. So, to heapify left and right child is compared with root node. And Swapping is performed to make the parent node with maximum value.

Example Explanation:

i=2, so left child is at i=4 and right child is at i=5. And array[4]=62 and array[5] =54. 62 is maximum among 54 and 63 and also greater than root node that is 19. Swapping will be done between i=2 and i=5 so that parent node is having maximum value than its child. Now, Heapification will be done below i=5 node. Left child of i=5 node is at i=10 and right child is at i=11. And 43 at i=11 is maximum among other 38(i=10) and 43(i=11), And 43 is also greater than parent node that is 19(i=5). So, again swapping will be done between i=5 and i=11. Now node at i=11 is leaf node, no more heapification will be performed. So now updated array is {81, 62, 76, 43, 54, 63, 66, 38, 19, 22}