Find the number of nodes of n-element heap of given height

Question

We have came across a question in Thomas H. Cormen which are asking for showing

Here I am confused by this question that how there will be at most nodes

For instance, consider this problem:

In the above problem at height 2 there are 2 nodes. But if we calculate by formula:

Greatest Integer of  (10/2^2+1) = 4 

it does not satisfy Thomas H. Cormen questions.

Please correct me if I am wrong here.

Thanks in Advance

Answer 1

In Tmh Corman I observed that he is doing height numbering from 1 not from 0 so the formula is correct, I was doing wrong Interpration. So leaf as height 1 and root has height 4 for above question

Answer 2

Reading all the answers, I realized that the confusion comes from the precise definition of height. In page 153 of CLRS book, the height is defined as follows:

Viewing a heap as a tree, we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf...

Now let's look at the original heap provided by Nishant. The nodes 8, 9, 10, 6, and 7 are at height 0 (i.e., leaves). The nodes 4, 5 and 3 are at height 1. For example, there is one edge between node 5 and its leaf, node 10. Also there is one edge between node 3 and its leaf node 6. Node 6 looks like it is at height 1 but it is at height 0 and hence a leaf. The node 2 is the only node at height 2. You may wonder node 1 (the root) is two edges away from node 6 and 7 (leaves), and say node 1 is also at height 2. But if we look back at the definition, the bold-face word "longest" suggests that the longest simple downward path from the root to a leaf has 3 edges (passing node 2). Finally, the node 1 is at height 3.

In summary, there are 5, 3, 1, 1 nodes at height 0, 1, 2, 3, respectively.

Let's apply the formula to the observation we made in the above paragraph. I would like to point out that the formula given by Nishant is not correct.

It should be ceiling(n/2^(h+1)) not ceiling(n/(2^h+1). Sorry about the terrible formatting. I am not able to post an image yet.

Anyways, using the correct formula,

h = 0, ceiling(10/2) = 5 (nodes 8, 9, 10, 6, and 7)
h = 1, ceiling(10/4) = 3 (nodes 4, 5 and 3)
h = 2, ceiling(10/8) = 2 (node 2, but this is okay because the formula is predicting that there are at most 2 nodes at height 2.)
h = 3, ceiling(10/16) = 1 (node 1)

With the correct definition of height, the formula works.