Question

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

EXPERT ANSWER

The number of edges on a simple downward path from a root to a leaf is the height of a binary heap.

Let the height of the {eq}n

{/eq}-element heap be {eq}h

{/eq}.

t

From the bounds on maximum and minimum number of elements in a heap, we get

{eq}2^h<=n<=2^(h+1)

{/eq}

Now taking logarithms to the base 2, we get

{eq}h<=log(n)<=h+1

{/eq}

Here we have {eq}n=210

{/eq} , so the height