2
$\begingroup$

Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.

Definition

A binary tree is ordered if the key at every node is smaller than the keys at its children.

An ordered binary tree of height $h$ is called a heap if the tree induced by all levels except the last is a complete binary tree and all leaves are "as much to the left as possible".

So what I've come up with is this expression:

$$C_h=\displaystyle\prod_{n=1}^{h} (2^{i-1})!$$

The intuition behind it is that with every increment by $1$ of $h$ the tree gains $2$ times more leaves than before and the possibilities of ordering these leaves can be determined via the factorial operation. Does that make sense?

$\endgroup$
  • $\begingroup$ What is a leftist heap? What is the "faculty operation"? $\endgroup$ – Yuval Filmus Jun 1 at 13:54
  • $\begingroup$ en.m.wikipedia.org/wiki/Leftist_tree I didn't translate correctly, it should've said factorial operation $\endgroup$ – Christian Singer Jun 1 at 13:59
  • $\begingroup$ Unfortunately, the Wikipedia article doesn't contain a definition of leftist heap – it just contains some equivocal "hints". I found a definition in some online slides: a heap is leftist if for each node, the rank of its left child is at least as large as the rank of its right child, where the rank of a node is the depth of the shallowest leaf in the subtree rooted at the node. $\endgroup$ – Yuval Filmus Jun 1 at 14:17
  • $\begingroup$ I can't really follow your argument. $\endgroup$ – Yuval Filmus Jun 1 at 14:18
  • $\begingroup$ Yes, what you've found explains it better. I had one explanation in my lecture notes which are in german unfortunately. What formula would you propose if mine seems to be based on a wrong approach ? $\endgroup$ – Christian Singer Jun 1 at 14:25
2
$\begingroup$

When $n = 2^h-1$, the heap is just a complete binary tree of height $h$. Clearly $C_0 = C_1 = 1$. For $h > 1$, we can decompose the heap as follows:

  • The root must be 1.
  • Each of the two children are heaps of size $2^{h-1}-1$ on their respective values.
  • The $2^h-2$ values other than the root can be divided arbitrarily to the two children (each gets exactly $2^{h-1}-1$).

This gives us the recurrence $$ C_h = \binom{2^h-2}{2^{h-1}-1} C_{h-1}^2. $$ Unrolling this recurrence gives $$ C_h = \binom{2^h-2}{2^{h-1}-1} \binom{2^{h-1}-2}{2^{h-2}-1}^2 \binom{2^{h-2}-2}{2^{h-3}-1}^4 \cdots \binom{2^1-2}{2^0-1}^{2^{h-1}}. $$ This is A056972. You can prove inductively that $$ C_h = \frac{(2^h-1)!}{\prod_{k=1}^h (2^k-1)^{2^{h-k}}}. $$ This formula also has a combinatorial interpretation. Start with one of the $(2^h-1)!$ possible permutations of keys. Swap the root with the minimal key (1), and then do the same recursively on both children. This gives a heap. Going in the other direction, we can start with a heap, and then go over all internal nodes in non-increasing order of depth, swapping the root with an arbitrary node in the subtree. There are $2^{h-k}$ nodes at depth $h-k$, and each of them has $2^k-1$ nodes at its subtree. This gives the denominator.

$\endgroup$
  • $\begingroup$ Upon reading this answer again, I still do not fully understand why we have to square the $C_{h-1}$ $\endgroup$ – Christian Singer Jun 3 at 9:13
  • 1
    $\begingroup$ Each heap of height $h$ consists of a root together with two heaps of height $h-1$. $\endgroup$ – Yuval Filmus Jun 3 at 9:21
  • $\begingroup$ Oh ok! I get it, hence we have to multiply $C_{h-1}$ with itself inorder to get all the combinations possible just like when you have 2 coins with heads and tails you have $(h1,h2) ; (h1,t2) ; (t1,h2) ; (t1,t2)$ as the 4 possible outcomes of the coin flips $\endgroup$ – Christian Singer Jun 3 at 9:31
3
$\begingroup$

The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$.

Instead of looking at the leaves, you should look at the root of the tree: since the tree is perfect, it has two children of size $2^{h-1}-1$ (this is how $C_{h-1}$ appears). You just have to think of how to split $2^{h}-2$ keys between left and right (the key of the root is uniquely determined, since it is a heap).

I will edit this answer if it is not clear enough.

$\endgroup$
  • $\begingroup$ Yes indeed, the definition of a complete tree fits the definition in my lecture notes. $\endgroup$ – Christian Singer Jun 1 at 14:48

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.