Suppose we want to use the Heapsort algorithm to sort a large list of numbers.

Our first step is to convert the input list to a heap. Then we run BUILD$-$MAX$-$HEAP, which applies MAX$-$HEAPIFY on the nodes in the heap, starting the last node and moving towards the top. $($Think about why we do it bottom$-$up instead of top$-$down.$)$

An example is provided on pg$.157$ of the textbook. In this example, A $=[4,1,3,2,16,9,10,14,8,7].$ The end result of BUILD$-$MAX$-$HEAP is $[16,14,10,8,7,9,3,2,4,1].$ I strongly encourage you to go through this example, step by step.

A total of $7$ swaps are made by BUILD$-$MAX$-$HEAP. You can check that the seven swaps occur in this order: $(14,2),(10,3),(16,1),(7,1),(16,4),(14,4),(8,4).$

Here is another way to see this: $2$ goes down one level, $3$ goes down one level, $1$ goes down two levels, and $4$ goes down three levels. Adding the underlined numbers, we see that the total number of swaps is $1+1+2+3=7.$

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

Determine BUILD$-$MAX$-$HEAP$($A$),$ and also determine the total number of swaps.