16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @DaveClarke: Not quite; the linked question is the result of a misunderstanding on us editors' parts left there for reference. $\endgroup$ – Raphael Mar 28 '12 at 6:45
  • $\begingroup$ Have you tried induction over node number resp. number of insertions? $\endgroup$ – Raphael Mar 28 '12 at 7:17
  • $\begingroup$ @DaveClarke: Why? It is a valid question in itself, imho. $\endgroup$ – Raphael Mar 28 '12 at 9:03
  • $\begingroup$ BTW, the question has nothing to do with heaps. The claim holds for any complete binary tree $\endgroup$ – Ran G. Mar 29 '12 at 6:07
8
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Note that full are different from complete are different from perfect binary trees. Unfortunate, ambiguous and inconsistent choice of words there, but what can you do about it. I guess sticking to Wikipedia's definition makes sense, as most will look there first? $\endgroup$ – Raphael Mar 28 '12 at 6:49
  • $\begingroup$ Oh, wow, I didn't even know these terms. Thanks for pointing this out. $\endgroup$ – Ran G. Mar 28 '12 at 7:22
  • $\begingroup$ "up to level k−1 the tree is perfect (and has 2^k − 1 nodes there)" and "Thus, out of the 2^(k−1) nodes at level k−1" seem to be conflicting statements, or am I missing something? $\endgroup$ – adrian h. Aug 12 '16 at 10:36
  • $\begingroup$ @adrianh. ($2^k-1$) nodes in the entire subtree, $2^{k-1}$ nodes only on the last level (thus in the entire subtree there are $2^{k-1}+2^{k-2}+...$ nodes.) $\endgroup$ – Ran G. Aug 12 '16 at 14:11
  • $\begingroup$ Ah you're completely right, thanks a lot for the clarification! $\endgroup$ – adrian h. Aug 13 '16 at 12:38
11
$\begingroup$

Here's a simpler logical proof.

Last leaf is $n^{th}$ index. Its parent is at index $\lfloor{n/2}\rfloor$ and similarly, there is no element such that its parent is ($\lfloor n/2 +1\rfloor)^{th}$ element. Thus leaves are indexed from $\lfloor{n/2}\rfloor$ +1 to n.

Hence, total number of leaves = n- $\lfloor(n/2)\rfloor$ = $\lceil(n/2)\rceil$.

$\endgroup$
  • 1
    $\begingroup$ Quite intuitive and clear explanation. Thanks. $\endgroup$ – whitehat Nov 18 '15 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.