data structure and algorithms

1. Heaps. (a) What are the minimum and maximum number of elements in a heap of height h? (b) Show that an n-element heap has height blog nc. (c) Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. (d) Is the sequence h23; 17; 14; 6; 13; 10; 1; 5; 7; 12i a max-heap? Why or why not? 2. Heaps. (a) Illustrate the operation of Max-Heapify(A; 3) on the array A = h27; 17; 3; 16; 13; 10; 1; 5; 7; 12; 4; 8; 9; 10i. (b) Illustrate the operation of Build-Max-Heap(A) on the array A = h5; 3; 17; 10; 84; 19; 6; 22; 9i. (c) You are given a list of numbers for which you need to construct a min-heap. How would you use an algorithm for constructing a max-heap to construct a min-heap? 3. Heapsort. Argue the correctness of Heapsort using the following loop invariant. At the start of each iteration of the for loop, the subarray A[1 : : : i] is a max-heap containing the i smallest elements of A[1 : : : n], and the subarray A[i+1 : : : n] contains the n