0
$\begingroup$

I don't understand the $T(2n / 3)$ part in the recurrence relation for MAX-HEAPIFY in the book CLRS. There is another post that explains it but I can't realize it.

$\endgroup$
4
  • $\begingroup$ Is it clear to you that $2n/3$ must be an upper bound to the size of the subtree you are recursing in? For an explanation of the constant cannot be lower than $2/3$ you can see this answer? If that's not clear, maybe you can be more explicit on what your confusion is $\endgroup$
    – Steven
    Commented Jul 8, 2021 at 14:14
  • $\begingroup$ @Steven I have seen the answer but I haven't understood it. No I can't understand why it's an upper bound. $\endgroup$
    – Emad
    Commented Jul 8, 2021 at 14:21
  • $\begingroup$ I'll try to write an answer showing how you can prove that. $\endgroup$
    – Steven
    Commented Jul 8, 2021 at 14:28
  • $\begingroup$ @Steven Thanks. $\endgroup$
    – Emad
    Commented Jul 8, 2021 at 14:29

2 Answers 2

1
$\begingroup$

Suppose that you are running MAX-HEAPIFY on some vertex $v$ of a heap $H$. Then the subtree $H_v$ rooted at $v$ is also a heap. Let $n$ be the number of vertices of $H_v$.

Clearly if $v$ has no children or only one (left) children then $T(n) = O(1)$ so let's focus on the case in which $v$ has two children $u$ and $w$, where $u$ is the left child and $w$ is the right child. Let $n_u$ be the number of vertices in $H_u$ and $n_w$ be the number of vertices in $H_w$.

Clearly the worst case happens when we choose to recurse on the subtree with most nodes between $H_u$ and $H_w$. By the properties of the heap we know that $n_u \ge n_w$ so we can restrict ourselves to the case in which we recurse on $H_u$.

The question now becomes: how large can $n_u$ be compared to $n$?

To answer this question let $h_v$ be the height of $H_v$. We know that the height $h_u$ of $H_u$ must be $h_v - 1$. Moreover, the height of $H_w$ can be either $h_v-1$ or $h_v-2$ (otherwise $H$ was not a complete binary tree).

The maximum number of nodes in a binary tree of a generic height $h$ is at most $2^{h+1}-1$ (which corresponds to a perfect binary tree binary tree). This tells us that $n_u \le 2^{h_u + 1} - 1 = 2^{h_v} - 1$.

Moreover, the number of nodes in a complete binary tree of height $h$ is at least $2^h$ (where $2^h - 1$ nodes are from a perfect binary tree of height $h-1$ and there must be at least one node on the $h$-th level). This tells us that $n_w \ge 2^{h_w} \ge 2^{h_v-2}$.

We are now ready to find the maximum possible ratio between $n_u$ and $n = n_u + n_w + 1$.

$$ \begin{align*} \frac{n_u}{n} &= \frac{n_u}{n_u + n_w + 1} \le \frac{n_u}{n_u + 2^{h_v-2} + 1} = 1 - \frac{2^{h_v-2} + 1}{n_u + 2^{h_v-2} + 1} \\ &\le 1 - \frac{2^{h_v-2} + 1}{2^{h_v-1} + 2^{h_v-2} + 1} = 1 - \frac{2^{h_v-2} + 1}{3 \cdot 2^{h_v-2} + 1} \\ & < 1 - \frac{2^{h_v-2} + 1}{3 \cdot ( 2^{h_v-2} + 1)} = 1 - \frac{1}{3} = \frac{2}{3}. \end{align*} $$

$\endgroup$
4
  • $\begingroup$ Excellent. I understand now. My problem was indexing. You modified it in this new answer. Thanks. $\endgroup$
    – Emad
    Commented Jul 8, 2021 at 16:54
  • $\begingroup$ We also get the same upper bound for MIN-HEAPIFY. Right? With the same proof. $\endgroup$
    – Emad
    Commented Jul 8, 2021 at 17:29
  • $\begingroup$ Yes, Min-Heaps and Max-Heap are completely symmetric. $\endgroup$
    – Steven
    Commented Jul 8, 2021 at 18:57
  • $\begingroup$ @Pallen thanks for the edit. $\endgroup$
    – Steven
    Commented Aug 11, 2023 at 22:53
1
$\begingroup$

Consider a tree $\mathcal{T}$ at root $\mathcal{r }$, and contain $\mathcal{n}$ nodes and $\mathcal{h}$ be height of $\mathcal{T}$ such that leaves are half full, so, without loss generality, suppose the left sub-tree $\ell$ of $\mathcal{T}$ is a full binary tree (i.e. leaves are half full).

(i) Now it's sufficient to show that ratio of $\ell$ to $n$ (i.e. $\frac{|\ell|}{n})$ is $\frac{2}{3}$.

Consequently the worst case of MAX-HEAPIFY happen when we recurse on $\ell$.

For showing (i), first of all, let the number of nodes in $\ell$ is: $$|\ell|=\sum_{i=0}^{\mathcal{h}-1}2^i=2^h-1$$ The number of nodes in $\mathcal{R}:$ $$|\mathcal{R}|=\sum_{i=0}^{\mathcal{h}-2}2^i=2^{h-1}-1$$ As a result $$n=|\ell|+|\mathcal{R}|+\mathcal{r }=|\ell|+|\mathcal{R}|+1=3\times 2^{h-1}-1$$ So $$\frac{|\ell|}{n}= \frac{2^{h-1}-1}{3\times 2^{h-1}-1}\leq \frac{2\times2^{h-1}}{3\times 2^{h-1}}=\frac{2}{3}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.