MaX$-$Heap$-$Extract$-$Max $(A),$ Max$-$Heap$-$Increase$-$Key $(A,i,k),$ and MaX$-$Heap$-$Insert $(A,k).$ Con$-$

sider the following operation MAx$-$HEAP$-$Delete$(A,i)$ which will remove the element at index i from a

max heap.

MAX$-$HEAP$-$Delete $(A,i)$

$1$ if $i>$ A$.$heapsize

error "index out of range"

MAX$-$HEAP$-$INCREASE$-$KEY $(A,i,)$

MAX$-$HEAP$-$EXTRACT$-$MAX $(A)$

Q$2$ a

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.

Q$2$ b

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.