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

Question

We ran into a question in Thomas H. Cormen asking to show

This question confuses me here: how will it be in most nodes

For example, consider this problem:

In the above problem, at a height of 2, there are 2 nodes. But if you calculate by the formula:

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

he does not satisfy the questions of Thomas H. Cormen .

Please correct me if I am wrong here.

Thanks at Advance

Answer 1

In Tmh Corman, I noticed that it makes the height numbering from 1, not from 0, so the formula is correct, I did the wrong Interpration. So the leaf is like height 1, and the root has height 4 for the above question

Answer 2

It looks like your formula says no more than [n / 2 ^ h + 1] nodes with height h. In your example, there are two nodes with a height of 2, which is less than the calculated maximum maximum of 4 (ish).

Answer 3

Reading all the answers, I realized that the confusion comes from accurately determining the height. On page 153 of the CLRS book, the height is defined as follows:

Looking at the heap as a tree, we determine the height of the node in the heap to be the number of edges on the long simplest descending path from node to leaf ...

Now look at the original heap provided by Nishant. Nodes 8, 9, 10, 6, and 7 are at a height of 0 (i.e., leaves). Nodes 4, 5 and 3 are at a height of 1. For example, between node 5 and its sheet, node 10 has one edge. There is also one edge between node 3 and its leaf node 6. node 6 looks like at a height of 1, but at a height of 0 and therefore on the sheet. node 2 is the only node at height 2. You might wonder that node 1 (root) is the two edges from node 6 and 7 (leaves), and they say that node 1 is also at height 2. But if we look back at definition, the word of the bold word "longest" assumes that the longest simple descending path from root to leaf has 3 edges (passing node 2). Finally, node 1 is at height 3.

Thus, there are 5, 3, 1, 1 nodes at a height of 0, 1, 2, 3, respectively.

We apply the formula to the observation we made in the previous paragraph. I would like to point out that the formula proposed by Nishant is incorrect.

It should be a ceiling (n / 2 ^ (h + 1)) not a ceiling (n / (2 ^ h + 1). Sorry for the awful formatting. I still cannot post the image.

In any case, 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 normal, because the formula predicts that at a height of no more than 2 nodes).

h = 3, ceiling (10/16) = 1 (node ​​1)

With the correct determination of height, this formula works.

Answer 4

When calculating the tight binding for Build-Max-Heap, the author used this property in the equation.
In this case, we call the Max-Heapify helper , which takes O (h ), where h is the height of the subtree root in the current node (not the height of the node relative to the full tree).
Therefore, if we consider the subtree rooted in the node leaf, it will have a height of 0, and the number of nodes in the tree at this level will be no more than n / 2 ⁰ +1 = n / 2 (i.e., h = 0 for under the tree formed from node in leaves).
Similarly, for a subtree embedded in the actual root, the height of the tree will be log (n), in which case the number of nodes at this level will be 1, i.e. gender n / 2 ^logn +1 = [n / n + 1].

Answer 5

Formula for

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

therefore, 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 

Therefore, there are two nodes that you can see from the figure.

Answer 6

Although Cormen mentions that the height of a node is the largest distance traveled from a node to a leaf (the number of edges) if you occupy the height to be the distance of the node from the leaf, i.e. the height of the leaf is zero, and in the root, the height is log (n). The formula is correct.

As for the leaves, you have h = 0; therefore, by the formula n / (2 ^ (h + 1)) h = 0; the maximum number of leaves per heap will be n / 2.

Answer 7

As for height 1. Cormen’s theory gives 10 / (2 ^ (1 + 1)) = 3 (ceil), and at a height of 1 - 4 knots. This is a contradiction.

Answer 8

It is not true that Thomas H. Cormen calculates the height of the tree, starting with one, the height h = 0, 1, ..., log n and it increases as you move up:

and in the following formula he added 1 plus height:

All the confusion comes from the fact that this will work well with Perfect Binary Trees , and not what you show in your question, so it says ON MOST

when you consider Big-O, it does not matter.

Answer 9

This formula is incorrect, it gives incorrect answers in many cases, for example, in this question for h = 1 (i.e. the second last level), it gives the maximum number of nodes 3, but there are 4 nodes. Also consider a tree with 4 nodes:

  a / \ bc / d 

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

4/2 ^ (1 + 1) = 1

which means that this level can have no more than 1 node, which is wrong!

therefore, this formula is incorrect.

Answer 10

The formula is absolutely correct. Nothing works with the formula! Let's take a tree (although its pile is not yet complete) in the question posed by Nishant from above. For h = 0 means that all leaves are so streams (10/2 ^ (0 + 1) = 5), therefore there are 5 leaves For h = 1 all nodes that have one arc reach the leaves, therefore ceil (10/2 ^ (1 + 1)) = 3 in your tree there are 3 such nodes. For h = 2, all nodes that have two consecutive arcs reach the leaves, so ceil (10/2 ^ (2 + 1)) = 1, so you only have one such node (left root successor) For h = 3, mean all nodes that have three arcs, so ceil (10/2 ^ (3 + 1)) = 1, which is the root.

The moral of the story is that you are confused between height and level. The level starts from the beginning. This means that you have 4 nodes at level 2. ie you can reach 4 nodes if you start from the root and move two arcs down. While the height is completely different. As in the above case, at a height of 0 there are 5 nodes (3 at level 3 and 2 at level 2). Therefore, the height of ha node n means how many arcs you can move to reach the leaf.

Respectfully,

Hope this clarifies the point.

Safdar from Pakistan