script

Thursday, January 10, 2013

Heap sort 2n/3 sub tree size


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.
Refrence : http://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

No comments:

Post a Comment