60

25

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

4

A simple calculation is provided at this blog: http://bit.ly/138f43F.

– akaHuman – 2013-06-26T12:28:39.957