a.

b.

c.

The Min-Heap property requires that the values stored at a node in a heap is smaller than or equal to the values stored at both its children. We have the following array to represent a min-heap (a heap with the Min-Heap prop- erty): 3 5 9 6 8 20 10 12 18 9 Draw the corresponding binary tree to represent this heap (Hint: Remember the indexing rules of heaps where the node for the item located at the i position would have the parent node located at position [i/2]). Similarly, the Max-Heap property requires that the values stored at a node in a heap is greater than or equal to the values stored at both its children (i.e., max-heap). The BUILD-MAX-HEAP method when being run on an array of n elements will convert it into a max-heap of n elements. What is the time complexity of this algorithm? Give the tightest available bound. Can the BUILD-MAX-HEAP method convert our array for a min-heap above to a max- heap? If yes, illustrate BUILD-MAX-HEAP on this array of n = 10 items. You may represent the heap as either an array or a tree. Show intermediate results after each call to MAX-HEAPIFY. 3 5 9 6 8 20 10 12 18 9