Question

(a) Find the smallest and the largest number of keys that a heap of height h can have. (b) Prove that the height of a heap with n nodes is [log2 n]

Answer 1

a)

Heap is a data structure which is an almost complete binary tree. which means that if tree is of height 'h' then all the nodes till height 'h-1' needs to be completely filled. Thus we can easily calculate the minimum number of keys required, which has to be all levels of 'h-1' filled plus one node at height 'h'.

Thus if a heap of height 'h' is considered we get minimum number of nodes as,

total number of nodes till height 'h-1' + one node at height 'h' = ($2^{h-1}$-1) + 1

= $2^{h-1}$

Thus smallest number of keys required for a heap of height h is $2^{h-1}$.

For maximum number of keys in a heap. The heap of height 'h' has to be completely filled. As per the definition it has to be a complete binary tree. Thus maximum number of nodes will be same as the number of nodes for a complete binary tree with height 'h'.

Thus, maximum number of keys equals to ($2^{h}$ -1)

b)

Now, from the above conclusions the minimum and maximum number of keys for a binary heap is $2^{h-1}$ and  ($2^{h}$ -1) respectively.

Thus, for a tree with 'n' number of nodes, it has to lie between then maximum and minimum number of nodes. Thus, we get the following relation.

$2^{h-1}$$\leq$ n  $\leq$ ($2^{h}$ -1)

Taking logarithms of base 2, we get

h-1  $\leq$
ogo n
  $\leq$ h //log 1 =0

Thus from this we conclude that, the height of binary heap with 'n' nodes follows  .

Og2 n

Thus height of heap with 'n' nodes is  .

Og2 n