# MAX-HEAPIFY - why the worst case is when the bottom level is "half full"?

In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says:

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.

I know how 2n/3 comes. However,

Can anyone please explain to me how

"the worst case occurs when the last row of the tree is exactly half full"?

Why half full? Why not full tree?

Thank you!

As you add more elements to the last row, you balance out the size of the two children subtrees, and thus push the proportion of elements in any one child to $1/2$.

You could always just do an algebraic calculation rather than "thinking it out", though:

• Let there be $k$ elements in the last row
• Compute the size of the largest child
• Find the maximum of the result from the previous step

Even if the tree is complete binary tree, the no. of nodes in both the sub-trees (left and right of node i) will be bounded by 2n/3. Since the algorithm will choose one of the sub tree of node i, it will not matter which sub-tree it chooses. The thing that matter is that sub-tree must be maximum size and since the size of max nodes subtree is bounded by 2n/3 we will get the same recurrence equation.

Though it might sound boring or redundant, we've to be very clear about the exact definitions because through attention to the details -- chances are that when you do that, proving things becomes much easier.

From CLRS section 6.1, The (binary) heap data structure is an array object that we can view as a nearly complete binary tree

From Wikipedia, In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Also, from Wikipedia, A balanced binary tree is a binary tree structure in which the left and right sub-trees of every node differ in height by no more than 1.

So, in comparison to root, the height of the left and right sub-tree can differ by 1 at max.

Now, Consider a tree T, and let the height of the left sub-tree = h+1 and the height of the right sub-tree = h

What's the worst-case in MAX_HEAPIFY? The worst-case is when we end up doing more comparisons and swaps while trying to maintain the heap property.

If the MAX_HEAPIFY algorithm runs and it recursively goes through the longest path, then we can consider a possible worst-case.

Well, all the longest paths are in the left sub-tree (as its height is h+1). Why not the right sub-tree? Remember the definition, all the nodes in the last level have to be as far left as possible.

So, to get more number of the longest paths we oughta make the left sub-tree FULL (Why? So that we can get more paths to choose from and opt for the path that gives the worst-case time). Since the left subtree is of height h+1, it will have 2^(h+1) leaf nodes and therefore 2^(h+1) longest paths from the root. This is the maximum possible number of longest paths in tree T (of h+1 height).

Here's the image of the tree structure in the worst-case situation.

From the above image, consider that the yellow(left) and pink(right) sub-trees have x nodes each. The pink portion is a complete right sub-tree and the yellow portion is the left sub-tree excluding the last level.

Notice that both the yellow(left) and the pink(right) sub-trees have height h.

Now, since the start, we've considered the left-subtree to be of height h+1 as a whole (including the yellow portion and the last level), if I may ask, how many nodes do we've to add in the last level i.e. below the yellow portion to make the left sub-tree completely full?

Well, the bottom-most layer of the yellow portion has ⌈x/2⌉ nodes (Total number of leaves in a tree/subtree having n nodes = ⌈n/2⌉; for a proof visit this link), and now if we add 2 children to each of these nodes/leaves, => total x (≈x) nodes have been added (How? ⌈x/2⌉ leaves * 2 ≈ x nodes).

With this addition, we make the left sub-tree of height h+1 (the yellow portion with height h + this one last level added) and FULL, hence meeting the worst-case criteria.

Since the left sub-tree is FULL, the whole Tree is half-full.

Now, the most important question -- why don't we add more nodes or add nodes in the right sub-tree? Well, that's because now if we tend to add more nodes, the nodes will have to be added in the right sub-tree (as the left sub-tree is FULL), which, in turn, will tend to balance out the tree more. Now as the tree is starting to get more balanced, we're tending to move towards the best-case scenario and not the worst-case.

Also, how many nodes do we have in total?

Total nodes of the tree n = x (from the yellow portion) + x (from the pink portion) + x (addition of the last level below the yellow portion) = 3x

Notice, as a by-product, that the left sub-tree in total contains at-most 2x nodes i.e. 2n/3 nodes (x = n/3).