# How to get this upper bound on worst-case heaps?

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1)$$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Update:

Trying to explain in more detail what I don't understand. As far as I know/remember for given $n$ that somehow measures how large is the input of an algorithm the worst case analysis is "choose among all the possible instances of size $n$ the one that would give you the worst case execution cost"

Following this direction, to me is not particular clear how for given $n$ we can be sure that the left subtree has $\frac{2n}{3}$ nodes, it is ok when the value $n$ is such that the distribution of nodes is such that half of the last level is full, while the other one is empty. In the proof for cost bounding I would differently.

I would distinguish two cases :

1. The tree has height $h$ and is complete, i.e. the total number of nodes is $2^{h+1} - 1$, I would also explain that it is possible to build in such case an heap such that starting from the root key it is possible to push down such key until it reach a leaf, how much is the cost in such case? it is exactly $h = ln_2(n+1) - 1 = O(ln \;n)$.

2. The tree has height $h$ but it is not complete, given the heap structure the left-most leaf is at height $h$. As done in point 1 I would explain it is possible to build a tree such that the root would be pushed down always in the left branch. How much is the cost in this case? Given that $n > 2^{h} - 1$ we have that $h < ln_2(n+1) = O(ln(n))$.

I don't think is difficult to build a particular example for both 1. and 2. I also don't really see the point of "completing a tree" for computing the worst case cost, I can understand this operation can make the analysis easier, but for what I know about worst case analysis (assuming it is correct) it doesn't sounds correct to me.

In Heap sort we use a data structure which is a binary tree, and it is nearly complete. So, height is bounded by $\log n$ where n is the no. of nodes. In comparison to root, height of left and right subtree can differ by 1 at max.

Now, Imagine a tree T, and also assume left subtree height = h+1 and right subtree height = h

What is worst case in max_heapify() ? Worst case is when , we end up doing more comparision and swaps while trying to gain heap property.

If the recursive max_heapify algorithm runs and it recursively goes to the longest path, then we can say : a possible worst case.

Well, all the longest paths are in the left sub-tree (because height is h+1 ).

So, to get more longest paths we need to have make left subtree completely full. Since left subtree is of height h+1 , it will have $2^{h+1}$ leaf nodes and $2^{h+1}$ longest paths from root. This is the maximum possible number of longest paths ( of h+1 height ) in T, such that while max_heapify() is running in a recursive way, it may traverse to the bottom of the left subtree. And we maximize such longest paths by considering left subtree as FULL to make the possibility of deep traversing more frequent in max_heapify() function.

Below is tree structure in worst case situation :

From the above figure assume yellow and red portions has x nodes each. Red portion is total right subtree and yellow portion is excluding the last level of left subtree. Both red and yellow sections now have height h.

How many nodes we have to add ( or attach or pad ) in the bottom layer of yellow portion to make the left subtree completely full as well as of height h+1 ?

Well, bottom layer of yellow portion has $\left&space;\lceil&space;\frac{x}{2}&space;\right&space;\rceil$ nodes and we now add 2 children to each of these nodes, => total x ( $\approx&space;x$) nodes have been added. Why adding, just to make left subtree of height h+1 and full to meet worst case criteria.

OK !! DONE !! .. now , count how many nodes overall...

total = $x&space;+&space;x&space;+&space;x&space;=&space;3x&space;=&space;n$

And left subtree contains 2x nodes = 2n/3 nodes.

So, for worst case one of the subtree should have 2n/3 nodes.

More in the following links : https://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

https://math.stackexchange.com/questions/181022/worst-case-analysis-of-max-heapify-procedure

• My issue with your answer is "Now, Imagine a tree T, and also assume left subtree height = h+1 and right subtree height = h", why having both left and right subtree at height "h+1" doesn't allow to instance a worst case example? Let's say you build an actual heap with the features you mentioned (so the recursive call would keep going through the left sub tree, but this would imply that the right subtree is also an Heap structure, right?), let's now say that you add a leaf in the right subtree such that the subtree is still an heap, why this would not be a worst case instance anymore? Aug 30, 2016 at 10:55
• Or is your discussion affected by the distribution of the nodes between the left/right subtrees? Should be such discussion interpreted as "for given number of nodes $n$ the worst case distribution of such nodes is "example". But again to me the worst case is only when the recursive call stops to the heap's leaves and if you make such hypothesis you would get the same asymptotic cost. Aug 30, 2016 at 11:01
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction.
– Raphael
Aug 30, 2016 at 11:09