confusion regarding heap sort

[sangfroid]

Hi,
I was going through MAX-HEAPIFY and I encounterd like this

The running time of MAX-HEAPIFY on a subtree of size n rooted at given node i is the Θ(1) time to fix up the relationships among the elements A[i], A[LEFT(i)], and A[RIGHT(i)], plus the time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i. The children's subtrees each have size at most 2n/3


I am not able to understand why children's subtrees each can have size at most equal to 2n/3 ? where this comes from ?????

[ajhampson]

The more mathematically inclined here can correct me, but I believe this is because you have a number of elements (n) that are stored in triplets (parent, left child, right child), thus the 3.

This seems to be an identity (sorry if I'm using the wrong term) of the max-heapify function; if the function is implemented correctly, this will be true. So, I wouldn't get too hung up on it.

alan