To analyze MAX$-$HEAPIFY, let $T(n)$ be the worst$-$case running time that the

procedure takes on a subtree of size at most $n.$ For a tree rooted at a given node $i,$

the running time is the $(1)$ time to fix up the relationships among the elements

$A[i],A[LEFT(i)],$ and $A[RIGHT(i)],$ plus the time to run MAX$-$HEAPIFY on a

subtree rooted at one of the children of node $i($assuming that the recursive call oc$-$

curs$).$ The children's subtrees each have size at most $2\frac{n}{3}($see Exercise $6\mathrm{.}2-2),$ and

therefore we can describe the running time of MAX$-$HEAPIFY by the recurrence

$T(n)T(2\frac{n}{3})+(1)$

The solution to this recurrence, by case $2$ of the master theorem $($Theorem $4\mathrm{.}1$ on

page $102),$ is $T(n)=O(lgn).$ Alternatively, we can characterize the running time

of MAX$-$HEAPIFY on a node of height $h$ as $O(h).$

Exercises

$6\mathrm{.}2-1$

Using Figure $6\mathrm{.}2$ as a model, illustrate the operation of MAx$-He\frac{a}{p}$I $Fy(A,3)$ on

the array $A=($:$27,17,3,16,13,10,1,5,7,12,4,8,9,0$:$).$

$6\mathrm{.}2-2$

Show that each child of the root of an $n-$node heap is the root of a subtree containing

at most $2\frac{n}{3}$ nodes. What is the smallest constant $$ such that each subtree has at

most $n$ nodes? How does that affect the recurrence $(6\mathrm{.}1)$ and its solution?

$6\mathrm{.}2-3$

Starting with the procedure MAX$-$HEAPIFY, write pseudocode for the procedure

MIN$-HE\frac{A}{P}$I $FY(A,i),$ which performs the corresponding manipulation on a min$-$

heap. How does the running time of MIN$-$HEAPIFY compare with that of MAX$-$

HEAPIFY?