1. As discussed in class, the min-heap data structure is symmetric to max-heap. In min-heap, the parent of each node other than the root is not greater than its children, i.e. A[PARENT(i)] A[i] for every node i other than the root. Similar to the pseudocode for MAX- HEAPIFY in pp. 154 of the textbook, the pseudocode for MIN-HEAPIFY is listed below.

// A recursive method to heapify a subtree with the root at given index i

// This method assumes that the subtrees are already heapified MIN-HEAPIFY(A, i)

1 int l = LEFT(i)

2 int r = RIGHT(i)

3 if l A.heap_size and A[l] < A[i]

4 smallest = l

5 else smallest = i

6 if r A.heap_size and A[r] < A[smallest]

7 smallest = r

8 if smallest i

9 exchange A[i] with A[smallest]

10 MIN-HEAPIFY(A, smallest)

a) [2 pts] Consider the integer array A = [10,2,9,5,6,11,12,7,8,9]. Give the nearly complete binary tree representation for the array A. You can do this by following the example on slide 7 of example-heap.pptx and filling the tree in a level by level manner. More concretely, A[i]s parent is A[i/2], and its left child and right child are A[2i] and A[2i+1] respectively whenever the indices are valid.

b) [3 pts] Draw the binary tree after you call MIN-HEAPIFY (A, 1) on the tree constructed in question a)