what is exactly meaning the formula n/2^h+1 in heap?

Question

Formula wrote in the site is :

And you can find it here: https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/

But I don't understand when your input is for example 7 (give n = 7) and hight of your heap is equal 2 the result is 7/8 !!!! and before the explained result show the number of nodes !? I can't understand what is meaning ?! can you explain to me?

Answer 1

A binary heap has at most ceil(n / (2 ^ (h + 1) ) ) nodes at height h. Following is an example of a binary tree with height 4

Size n = 31, since there are 31 nodes in total.

Coming to your question, let us count the maximum number of nodes at height h = 0 using the formula

=> ceil(n / ( (2 ^ (h + 1) ) )

= ceil(31 / (2 ^ (0 + 1) ) )

= ceil(31 / 2)

= 16

Also, it is evident from the tree, there are 16 nodes in total at height h = 0, which confirms our idea.

Plugging in h = 1, h = 2, h = 3, and h = 4 give 8, 4, 2, and 1 respectively, which is again consistent with our binary tree.