Proving a binary heap has $\lceil n/2 \rceil$ leaves

Question Detail: 

I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way:

Each new node is inserted via percolate up. This means that each new node must be created at the next available child. What I mean by this is that children are filled level-down, and left to right. For example, the following heap:

    0    / \   1   2 

would have to have been built in this order: 0, 1, 2. (The numbers are just indexes, they give no indication of the actual data held in that node.)

This has two important implications:

1. There can exist no node on level $k+1$ without level $k$ being completely filled

2. Because children are built left to right, there can be no "empty spaces" between the nodes on level $k+1$, or situations like the following:

       0    / \   1   2  / \   \ 3  4    6 

(This would be an illegal heap by my definition.) Thus, a good way to think of this heap is an array implementation of a heap, where there can't be any "jumps" in indeces of the array.

So, I was thinking induction would probably be a good way to do this... Perhaps something having to deal with even an odd cases for n. For example, some induction using the fact that even heaps built in this fashion must have an internal node with one child for an even n, and no such nodes for an odd n. Ideas?

Asked By : varatis

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/841

Answered By : Ran G.

If I get your question correctly, the obtained heap is just an ordered binary-tree, where in ordered I mean that the $k$th level can only be occupied after the $k-1$ level has been completely filled, and each level is occupied from left to right, without skipping.

Then the proof goes like this.

1. A perfect tree of depth $k$ has exactly $2^{k+1}-1$ nodes.
2. Assume that the heap reaches depth $k$. Thus
   1. up to level $k-1$ the tree is perfect (and has $2^k-1$ nodes there)
   2. on the last level, there are exactly $n-2^k+1$ nodes, which are all leaves.
3. Each leaf on the $k$th level has a parent. Moreover, each two consecutive leaves have the same father (maybe except for the last node, whose father has only one child)
4. Thus, out of the $2^{k-1}$ nodes at level $k-1$, $\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$ are parents, and the rest $2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$ are leaves.
5. The total amount of leaves is $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$ Which gives you what you need.