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

It is not true that Thomas H. Cormen is counting the height of the tree starting from one, height is h = 0, 1, ..., log n and it increases as you go upwards:

and in the following formula, he added 1 plus the height:

All the confusion is coming from the fact that this will work nicely with Perfect Binary Trees, not with the one you are showing in your question, this is why he is saying ON MOST

when you consider Big-O it wouldn't really matter

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.

Answer 3

The formula is quite correct. Nothing is wrong with the formula!! Lets take the tree(although its not heap yet its complete) in the question posed by Nishant on the top. For h=0 means all leaves so ceil(10/2^(0+1)=5) so there are 5 leaves For h=1 means all nodes which have one arc to reach the leaves, so ceil(10/2^(1+1))=3 there are 3 such nodes in your tree. For h=2 means all nodes which have two consecutive arcs to reach leaves, so ceil(10/2^(2+1))=1 so you have only one such node(left successor of the root) For h=3 means all nodes which have three arcs to leaves, so ceil(10/2^(3+1))=1 which is the root.

Moral of the story is that you are confused between height and level. Level starts from up to down. Which means you have 4 nodes on level 2. i.e you can reach 4 nodes if you start at root and moves two arcs down. Whereas height is completely different. Like in above case at height 0 there are 5 nodes (3 on level 3, and 2 on level 2). Hence height h of a node n means how many arcs you can travel to reach a leaf.

regards,

Hope it clarifies the point.

Safdar from Pakistan

Answer 4

This formula is wrong, it gives wrong answers in many cases like in this question for h=1 (ie second last level) it gives maximum number of nodes is 3 but there are 4 nodes. Also let us consider a tree with 4 nodes :

             a
            / \
           b   c
          /
         d

node d has height 0, let us consider for height =1 using the formula n/2^(h+1) we get

4/2^(1+1) = 1

which means this level can have at most 1 node which is false !

so this formula is not right.

Answer 5

what about height 1. Cormen's theory gives 10/(2^(1+1))=3(ceil) while there is 4 nodes at height 1. This is a contradiction.

Answer 6

Though it is mentioned in Cormen that height of a node is the greatest distance traveled from node to leaf(the number of edges), if you take height to be the distance of a node from the leaf, i.e. at leaf the height is zero and at root the height is log(n). The formula stands correct.

As for the leaves you have h=0; hence by the formula n/(2^(h+1)) h=0; max number of leaves in the heap will be n/2.

Answer 7

Formula for

no. of nodes = n/(2^(h+1)) 

so when h is 2, and n = 10

no. of nodes = 10/(2^(2+1)) = 10/(2^3) = 10/8 = 1.25

But

ceil of 10/8 = 2

Hence there are 2 nodes which you can see from the figure.

Answer 8

While calculating the tight bound for Build-Max-Heap author has used this property in the equation.
In this case we call the helper Max-Heapify which takes O(h) where h is the height of the sub-tree rooted at the current node (not the height of node itself with respect to the full tree).
Therefore if we consider the sub tree rooted at leaf node, it will have height 0 and number of nodes in the tree at that level would be at most n / 2⁰+1 = n/2 (i.e h=0 for the sub tree formed from node at leaves).
Similarly for sub-tree rooted at actual root the height of the tree would be log(n) and in that case the number of nodes at that level would be 1 i.e floor of n / 2^logn+1 = [n/n+1].

Answer 9

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 10

It looks like your formula says there are at most [n/2^h+1] nodes of height h. In your example there are two nodes of height 2, which is less than your computed possible maximum of 4(ish).