Question $4(20\mathrm{.}0$ marks$)$

a$.$ The operation $()$ converts a maximum heap into a minimum heap.

Design an algorithm of $$ that runs in $($ lg $)$ time. Show that your

algorithm runs in $($ lg $).$

$(10\mathrm{.}0$ marks$)$

b$.$ Given the following maximum heap, illustrate the process of converting it into a

minimum heap using your algorithm described in $($a$).$ You need to show the

intermediate processes. $(10\mathrm{.}0$ marks$)$

$19$

$171069$

$53$

$22$

$84$