Suppose that a heap stores 210 elements What is its heightSo

Suppose that a heap stores 210 elements. What is its height?

Solution

The maximum number of nodes at level l of the heap is 2^l .

So a heap of height h stores at most 2⁰ + 2¹ + . + 2^h = 2^h+1 1 nodes.

If h = 6, then the heap stores at most 27 1 = 127 elements, which is not enough.

So the heap must be of height 7, because for height 7 a heap can store 28 1 = 255.

The last level of the heap is not full, in this particular case, since it only has 210 elements.

So the height of the heap is 7.