2
$\begingroup$

I have a question about one of my homework assignments. I have to prove the following:

Prove by induction that a heap with $n$ vertices has exactly $\lceil \frac{n}{2} \rceil$ leaves.

This is how I am thinking right now:

(Basis) $n = 1$, $\lceil 1/2 \rceil = 1$ (trivial)
(Step) $n > 1$, We assume that a heap with $n$ vertices has $\lceil \frac{n}{2} \rceil$ leaves (IH).
When have $n+1$ leaves we can distinguish two cases:

  • Either the new vertex is even:
    When it is even, we have that $\lceil \frac{n+1}{2} \rceil$ = $\lceil \frac{n}{2} \rceil$.
  • Or it will be uneven



I'm not even sure if this is the right way, or how to prove this correctly. I'm hoping for some hints/tips. Thank you in advance.

1 Answers 1

3

Yes, it is the right way. Make a picture. Then you will notice that when you add an odd vertex then you just add a leaf to a vertex with one son (which is a leaf), what increases the number of leaves by one. If you add an even leaf to the heap, then you add this leaf to a vertex which was a leaf before this operation, so the total number of leaves is the same.

Additional hint: Is the number of vertices in a complete level in a heap even or odd?

  • 0
    @savick01: Makes sense, thank you and $+1$.2012-02-19