Question

Can you explain clearly?

Proving that a heap of has at least 2^h induction?

Answer 1

Base Case:  H = 0.  A binary heap of height 0 is just a single node with
no children, and therefore has 1 leaf.  1 = 2^0, so the base case
satisfies the induction hypothesis (see below).

Induction Hypothesis:  Suppose that for some k >= 0, all binary heaps of
height <= k have at most 2^k leaves.

Induction Step:  Let T be a binary heap of height k+1.  Then T's left and
right subtrees are each binary heaps of height <= k, and thus by the I.H.
have at most 2^k leaves.  The number of leaves in T is equal to the sum of
the number of leaves in T's subtrees, which must be less than or equal to
2^k + 2^k = 2^(k+1).  Hence the hypothesis holds for k+1, and so the
theorem is proved.