What are the minimum and maximum numbers of elements in a heap of height h?
Since a heap is binary tree the idea is to write in the power of 2. The minimum no of nodes for height h tree is (the tree has to have 1 node to left)$$\{1+2+2^2+....+2^{h-1}\}+1$$ The above series in the flower braces can be written as a geometric series Below is the formula for geometric series(see wikipedia): $$1-r^{n+1}/1-r$$ $$ \{1-2^{h-1+1}/1-2\} + 1 $$ $$ \{1-2^{h}/-1\} + 1 $$ $$ \{2{h}-1 \}+ 1 $$ $$ 2{h}$$ The maximum no of nodes for a height h tree is $$1+2+2^2+....+2^{h}$$ Below is the formula for geometric series(see wikipedia): $$1-r^{n+1}/1-r$$ $$ 1-2^{h+1}/1-2 $$ $$ 1-2^{h+1}/-1 $$ $$ 2^{h+1} -1 $$
No comments:
Post a Comment