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

Question

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 worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"

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

A simple calculation is provided at this blog: http://bit.ly/138f43F. — akaHuman, Jun 26 '13 at 12:28

score 71 · Accepted Answer · edited Aug 22 '12 at 05:22

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.

yeah, i get it, you mean L / n = 2/3 – Jackson Tale Feb 01 '12 at 16:42 — Jackson Tale, Feb 01 '12 at 16:42
Wow. That was deep. How did you figure it out by yourself? – Programming Noob Oct 15 '12 at 07:33 — Programming Noob, Oct 15 '12 at 07:33

score 38 · Answer 2 · answered Aug 02 '14 at 15:29

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.

I still don't understand. Won't it not happen even if it is full , why it has to be half full. someone explain - I am confused. — Sundar Rajan, May 19 '18 at 10:13
@SundarRajan check https://math.stackexchange.com/questions/181022/worst-case-analysis-of-max-heapify-procedure Especially the part `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` — momo, May 24 '18 at 12:03

score 14 · Answer 3 · answered Aug 31 '12 at 12:37

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)

Excellent answer. Please correct the f(h) as mentioned by @afnrf — Ajay, Aug 29 '14 at 02:58

score 2 · Answer 4 · answered Feb 12 '14 at 14:07

2

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

answered Feb 12 '14 at 14:07

Neo M Hacker

899
7
11

score 2 · Answer 5 · answered Dec 05 '15 at 23:15

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.

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

5 Answers5

Linked