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.