Worst case in Max-Heapify - How do you get 2n/3?

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,

> The children’s subtrees each have size at most 2n/3—the worst case > occurs when the bottom level of the tree is exactly half full.

I understand why it is worst when the bottom level of the tree is exactly half full. And it is also answered in this question https://stackoverflow.com/questions/6859514/worst-case-in-max-heapify

My question is how to get 2n/3?

Why if the bottom level is half full, then the size of the child tree is up to 2n/3?

How to calculate that?

Thanks

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

Once that is clear, the bound of 2N/3 is easy to get.

Let us assume that the total number of nodes in the tree is N.

>Number of nodes in the tree = 1 + (Number of nodes in Left Subtree) + (Number of nodes in Right Subtree)

For our case where the tree has last level half full, iF we assume that the right subtree is of height h, then the left subtree if of height (h+1):

Number of nodes in Left Subtree =1+2+4+8....2^(h+1)=2^(h+2)-1 .....(i)

Number of nodes in Right Subtree =1+2+4+8....2^(h) =2^(h+1)-1 .....(ii)

Thus, plugging into:

Number of nodes in the tree = 1 + (Number of nodes in Left Subtree) + (Number of nodes in Right Subtree)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

Plugging in this value into equation (i), we get:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

Hence the upper bound on the maximum number of nodes in a subtree for a tree with N nodes is 2N/3.

For a complete binary tree of height h, number of nodes is f(h) = 2^h - 1. In above case we have nearly complete binary tree with bottom half full. We can visualize this as collection of root + left complete tree + right complete tree. If height of original tree is h, then height of left is h - 1 and right is h - 2. So equation becomes

n = 1 + f(h-1) + f(h-2) (1)

We want to solve above for f(h-1) expressed as in terms of n

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

Using above in (1) we have

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

Hence O(2n/3)

To add to swen's answer. How (2k + 1) / (3k + 2) tends to 2 / 3, when k tends to infinity,

Lim_(k -> inf) (2k + 1) / (3k + 2) = Lim_(k -> inf) k(2 + 1 / k) / k(3 + 2 / k) = Lim_(k -> inf) (2 + 1 / k) / (3 + 2 / k)

apply the limit, and you get 2/3

Number of nodes at -

• level 0 i.e. root is 2^0
• level 1 is 2^1
• level 2 is 2^2
• ...
• level n is 2^n

Summation of all nodes from level 0 up to level n,

• S = 2^0 + 2^1 + 2^2 + ... + 2^n

From geometric series summation rule we know that

• x^0 + x^1 + x^2 + ... + x^(n) = (x^(n+1) - 1)/(x-1)

Substituting x = 2, we get

• S = 2^(n+1) - 1. i.e. 2^(n+1) = S + 1

As 2^(n+1) is the total nodes at level n+1, we can say that the number of nodes with 0 children is one more than the number of nodes with 2 children.

Now lets calculate number of nodes in left subtree, right tree and total ..

• Assume that number of non-leaf nodes in the left subtree of root = k.

• By the above reasoning, number of leaf nodes in the left subtree or root = k + 1. Number of non-leaf nodes in the right subtree of root = k as the tree is said to be exactly half full.

• Total number of nodes in the left subtree of root = k + k + 1 = 2k +

• Total number of nodes in the tree, n = (2k + 1) + k + 1 = 3k + 2.

• Ratio of nodes in the left subtree and total nodes = (2k + 1) / (3k + 2) which is bounded above by 2/3.

That's the reason of saying that the children’s subtrees each have size at most 2n/3.