Suppose that a heap stores 210 elements What is its height s

Suppose that a heap stores 210 elements. What is its height? (show work with diagrams)

Solution

A binary heap is a complete binary tree which satisfies the heap ordering property.

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

Therefore a heap of height h stores at most 2⁰+ 2¹+:+ 2^h= 2^{h +1} – 1 node.

If h= 6, then the heap stores at most 2⁷ – 1 =127 elements, which is not enough .so the heap must be of height 7,since for height 7 a heap can store 2⁸ – 1 =255. The last level of the heap is not full.