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$