First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most give a mathematical answer, but can't give a real example.
In CLRS 3ed pg 155 we have "The running time of MAX-HEAPIFY on a subtree of size n rooted at a given node i is the $\Theta(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 occurs). The children’s subtrees each have size at most $2n/3$ - $\textbf{the worst case occurs when the bottom level of the tree is exactly half full}$ — and therefore we can describe the running time of MAX-HEAPIFY by the recurrence $T(n) \leq T(2n/3) + \Theta(1)$.
I understand why the maximum nodes a subtree can have is around $2n/3$. I have two questions:
1) We're dealing with a heap - a "binary tree that is completely filled on all levels except possibly the lowest, which is filled from the left up to a point" (CLRS pg 151). For a given n, there's only one legal tree structure - we can't "make" its bottom level exactly half full. So what does it mean to say the worst run-time for n is when the bottom level is exactly full? If you mean that the worst-case happens when n is such that the bottom-level is half-filled, then it's worse in comparison to what? trees of other sizes? obviously different sizes have different run-times!
2) I understand why when there's a height difference it'll take another MaxHeapify call, but why does the bottom level have to be full? Can you give me an example of two trees of height larger than 1, where in one its bottom level is half-full, and in the other it's almost half-full (missing just one leaf from being half-full) and there's a worse run-time in the first one?