7. The heap algorithm BUILD-HEAP starts with an array A[1..n] of n random elements and establishes a valid min-heap of n elements. In this problem, we will see how this may be done in O(n) time using a divide-and-conquer approach. The algorithm is described recursively as follows. The parameter r in this recursive algorithm is the index of the root of the tree (or subtree) that needs to be built from scratch. The intial call to this algorithm is with r = 1, that is BUILD-HEAP(A,1, n). BUILD-HEAP (dtype A[ ], int r, int n) { if (2 *s > n) return; //Return if r is a leaf node (or non-existing) BUILD-HEAP(A, 2*r, n) //Build heap of left subtree BUILD-HEAP(A, 2*r +1, n) //Build heap of right subtree PUSHDOWN (A, r, n) //Now pushdown the root. (a) To analyze BUILD-HEAP, let f(n) be the worst-case number of SWAP operations to build a heap of n elements, starting with the initial call BUILD-HEAP(A, 1, n). To simplify the analysis, Suppose that the tree is a full-binary-tree. So the number of nodes in the left and right subtrees each is (n 1)/2 = (n/2] 1 0, n=1. Prove by induction that the solution is f(n) = An + Blog n + C and find the constants A, B, C. (b) Illustrate the recursive BUILD-HEAP algorithm on the following example: A[1..13] = (13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1). Show the array in the form of a tree. Show the result after each PUSHDOWN. (c) Write a non-recursive version of BUILD-HEAP (with a series of calls to PUSHDOWN). (d) Illustrate the non-recursive BUILD-HEAP for the array A[1..13] = (13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1). Show the intial tree, and the result after each PUSHDOWN is completed. 7. The heap algorithm BUILD-HEAP starts with an array A[1..n] of n random elements and establishes a valid min-heap of n elements. In this problem, we will see how this may be done in O(n) time using a divide-and-conquer approach. The algorithm is described recursively as follows. The parameter r in this recursive algorithm is the index of the root of the tree (or subtree) that needs to be built from scratch. The intial call to this algorithm is with r = 1, that is BUILD-HEAP(A,1, n). BUILD-HEAP (dtype A[ ], int r, int n) { if (2 *s > n) return; //Return if r is a leaf node (or non-existing) BUILD-HEAP(A, 2*r, n) //Build heap of left subtree BUILD-HEAP(A, 2*r +1, n) //Build heap of right subtree PUSHDOWN (A, r, n) //Now pushdown the root. (a) To analyze BUILD-HEAP, let f(n) be the worst-case number of SWAP operations to build a heap of n elements, starting with the initial call BUILD-HEAP(A, 1, n). To simplify the analysis, Suppose that the tree is a full-binary-tree. So the number of nodes in the left and right subtrees each is (n 1)/2 = (n/2] 1 0, n=1. Prove by induction that the solution is f(n) = An + Blog n + C and find the constants A, B, C. (b) Illustrate the recursive BUILD-HEAP algorithm on the following example: A[1..13] = (13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1). Show the array in the form of a tree. Show the result after each PUSHDOWN. (c) Write a non-recursive version of BUILD-HEAP (with a series of calls to PUSHDOWN). (d) Illustrate the non-recursive BUILD-HEAP for the array A[1..13] = (13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1). Show the intial tree, and the result after each PUSHDOWN is completed<><>