cormen (self doubt)(heap tree)

Question

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—and therefore we can describe the
running time of MAX-HEAPIFY by the recurrence
T (n) =T (2n/3) + constant

thats is the equation of max hepify but i dont understand the how it is divided in (2n/3).

plz explain

Answer 1

Look at the root node, it has two sub trees, LST and RST. Bottom of the level is exactly half full. LST contains 2n/3 nodes. ths tree contains three parts each of size n/3. 
first part: right sub tree
2nd part: left sub tree internal nodes
3rd part: left sub tree leaf nodes

2nd and 3rd part together make total 2n/3 left side. Maxheapify will be called at the root node.

Comments

thank u

---

Nice Explaination