Question $3$: Heaps

$.$

$($a$)10$ points Below are three different methods for building a max$-$heap. Suppose that A$[1,2,...,$ n$]$

initially contains n elements, which are not necessarily in heap format. You may assume that the value of A$.$heapsize $=$ n$.$ For each method, justify whether the method correctly. builds a max$-$heap. If so$,$ justify your answer. If not, provide an example showing it doesn$$t work.

METHOD $1$:

Initial call: Make$-$Heap$1($A$,$ n$)$ Make$-$Heap$1($A$,$ i$)$

If i $>1$ Bubble$-$up$($A$,$i$)$

Make$-$Heap$1($A$,$i $1)$

METHOD $2$:

Initial call: Make$-$Heap$2($A$,$ n$)$ Make$-$Heap$2($A$,$ i$)$

If i $1$ Bubble$-$down$($A$,$i$)$ Make$-$Heap$2($A$,$i $1)$

METHOD $3$:

Initial call: Make$-$Heap$3($A$,1)$ Make$-$Heap$3($A$,$ i$)$

If i $$ A$.$heapsize Bubble$-$up$($A$,$i$)$

Make$-$Heap$3($A$,$i $+1)$

$($b$)8$ points A min$-$max$-$heap is a complete binary tree containing alternating min and max levels. The root node is the minimum of all nodes in the tree. The nodes at the next level are the largest nodes of their subtrees. For each level after that, a node that is on a min level is the minimum of all nodes in its subtree, and a node that is on a max level, is the maximum of all nodes in its subtree. Below is an example of a min$-$max tree. Assume that the elements are stored in array A$[]$ as for usual heaps, where A$.$heapsize indicates the size of the heap. Your job is write the pseudo$-$code for a procedure that inserts into this type of heap. Call your procedure MinMaxInsert$($A$,$ k$),$ which inserts k into the heap, and carries out the necessary swaps in order to maintain the min$-$max heap property.

$($c$)6$ points Suppose A is a sorted list of exactly n elements, sorted in decreasing order. Suppose B a max$-$heap of exactly n elements. Two students are given the task of creating a sorted list of the combined elements from set A and B$.$ Below are their approaches:

Student $1$: Add all elements of A and B to a new array C of size $2$n$.$ Then uses bottom$-$up heap building, resulting in a max heap in array C$.$ Next, run HeapSort on array C$.$

Student $2$: Repeat until A and B are empty: Compare first element of A with element B$[1].$ If top element of A is larger, extract it to the output list. If B$[1]$ is larger, call Delete$-$max, and store to the output list. If at some point B is empty, simply concatenate all remaining elements of A to the output list. If at some point A is empty, continue calling Delete$-$max on B until it is empty.

Determine the worst$-$case runtime for each method above. Is there one student with a more efficient approach?