$T(n)=\{\begin{array}{ccc}1& \text{f}\text{o}\text{r}& n3\\ 4T(\frac{n}{2})+nlogn& \text{f}\text{o}\text{R}& \end{array}$

a$.(6$ points$)$ Given a max$-$heap represented by array $A[1.\mathrm{.}7]=($:$9,6,8,3,5,4,2$:$),$ perform MAx$-$HEAP$-$

Delete$(A,2)$ to remove the element $\text{'}6\text{'}$ from the heap. Show the updated array after each step $($a swap

or a key value change$).$ For each step, draw the corresponding binary tree representation along with the

updated array.

b$.(4$ points$)$ Analyze the running time of algorithm MAX$-$HEAP$-$Delete $($in terms of heap size $n).$ If the

best$-$case and worst$-$case running times differ, specify each using $$ notation, and describe the scenarios

that lead to the best$-$case and worst$-$case performance.