Problem $5($Generic BottomUpHeap$)$

Recall problem $2$ of Homework $2,$ where we had a generic compare function and the following

input array, that we inserted into the heap one by one by calling upheap:

$A=[17,3,7,2,9,11,13,5,10,16,1,6,4,8,12,14,15]$

Now we plan to create a heap with the same inputs and the same generic compare function, but

using the faster BuildHeap algorithm that's based on downheap rather than upheap operations.

This will be an in$-$place algorithm. Note that in the book, this is also called BottomUpHeap.

Show the contents of A after each call to downheap that Generic BottomUpHeap will make. Use

rounded arrows to show all the swaps that took place between successive version of $A.$

Hint: while we are asking for A$,$ you can also show us the corresponding binary tree, too. As a

"sanity check", make sure that the final binary tree constitutes a properly ordered heap according

to our compare function.