Worst case analysis of MAX-HEAPIFY procedure .

Start with a heap $H$ with $n$ levels with all levels full. That's $2^{i - 1}$ nodes for each level $i$ for a total of $$|H| = 2^n - 1$$ nodes in the heap. Let $L$ denote the left sub-heap of the root and $R$ denote the right sub-heap. $L$ has a total of $$|L| = 2^{n - 1} - 1$$ nodes, as does $R$. Since a binary heap is a complete binary tree, then new nodes must be added such that after heapification, nodes fill up the last level from left to right. So, let's add nodes to $L$ so that a new level is filled and let's denote this modified sub-heap as $L'$ and the modified whole heap as $H'$. This addition will require $2^{n - 1}$ nodes, bringing the total number of nodes in $L'$ to $$ |L'| = (2^{n - 1} - 1) + 2^{n - 1} = 2\cdot 2^{n - 1} - 1$$ and the total number of nodes in the entire heap to $$ |H'| = (2^{n} - 1) + 2^{n - 1} = 2^n + 2^{n - 1} - 1 $$

The amount of space $L'$ takes up out of the whole heap $H'$ is given by $$ \frac{|L'|}{|H'|} = \frac{2\cdot 2^{n-1} - 1}{2^n + 2^{n - 1} - 1} = \frac{2\cdot 2^{n-1} - 1}{2\cdot 2^{n - 1} + 2^{n - 1} - 1} = \frac{2\cdot 2^{n-1} - 1}{3\cdot 2^{n - 1} - 1} $$

Taking the limit as $n \to \infty$, we get: $$ \lim_{n\to\infty} { \frac{|L'|}{|H'|} } = \lim_{n\to\infty} { \frac{2\cdot 2^{n-1} - 1}{3\cdot 2^{n - 1} - 1} } = \frac{2}{3} $$

Long story short, $L'$ and $R$ make up effectively the entire heap. $|L'|$ has twice as many elements as $R$ so it makes up $\frac{2}{3}$ of the heap while $R$ makes up the other $\frac{1}{3}$.

This $\frac{2}{3}$ of the heap corresponds to having the last level of the heap half full from left to right. This is the most the heap can get imbalanced; adding another node will either begin to rebalance the heap (by filling out the other, right, half of the last level) or break the heap's shape property of being a complete binary tree.

The worst case scenario will occur when the recursive function MAX-HEAPIFY will be called until a leaf is reached.So to make it reach to the leaf we can choose the value of nodes such that every time the parent node is less then its children eg. chose parent node value as $0$ and every other node as $1$.So the running time will be $\Theta(h)=\Theta(\lg n)$ (since MAX-HEAPIFY will be called $h$ number of times and each call takes $\Theta(1)$ time).

Now as the running time is analysed by number of nodes in the tree ($n$).We have to maximize the number of nodes in the subtree so that the height will also get increased.So, $$T(n) \leq T(2n/3) + \Theta(1)$$ So in the worst case if we want to maximize the nodes in any of the subtree then we will make the final row of that subtree as full as possible and other subtree's final row as empty as possible.And by simple mathematical calculation we can show that - maximum number of node in a subtree is bounded by $2n/3$

We first note that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes. Note that the height of a tree is the maximum number of edges from the root to a leaf.

We see that the worst case of Max-Heapify occurs when we start at the root of a heap and recurse all the way to a leaf. We also see that Max-Heapify makes a choice of recursing to its left subtree or its right subtree. When Max-Heapify recurses it cuts the work down by some fraction of the work it had before. We will show that this fraction is at most $2/3$.

From inspection we see the worst ratio occurs when we are at the root node of a heap of height $h$ and the left subtree is a complete binary tree of height $h-1$ and the right subtree is a complete binary tree of height $h-2$. Notice this means the heap's last level is half full and the heap is of size $1+(2^h-1)+(2^{h-1}-1)$. If Max-Heapify chooses to recurse to its left subtree then the work has been cut by a factor of

\begin{align} \frac{\text{number of nodes in left subtree}}{\text{number of nodes in entire heap}} &= \frac{2^h-1}{1+(2^h-1)+(2^{h-1}-1)} \\ &= \frac{2^h-1}{2^{h-1}(2+1)-1} \\ &= \frac{2^h-1}{3\cdot2^{h-1}-1}. \end{align}

We now want to take the limit as $h\to\infty$ to get an upper bound on the ratio

$$ \lim_{h\to\infty}\frac{2^h-1}{3\cdot2^{h-1}-1} = \lim_{h\to\infty}\frac{2\cdot2^{h-1}-1}{3\cdot2^{h-1}-1} = \frac{2}{3}. $$

And so we see what the authors meant when they said "The children's subtrees each have size at most $2n/3$ - the worst case occurs when the last row of the tree is exactly half full".