# Number of possible heaps on $\{1,…,2^h-1\}$

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?

• What is a leftist heap? What is the "faculty operation"? – Yuval Filmus Jun 1 at 13:54
• en.m.wikipedia.org/wiki/Leftist_tree I didn't translate correctly, it should've said factorial operation – Christian Singer Jun 1 at 13:59
• 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. – Yuval Filmus Jun 1 at 14:17
• I can't really follow your argument. – Yuval Filmus Jun 1 at 14:18
• 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 ? – Christian Singer Jun 1 at 14:25

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.

• Upon reading this answer again, I still do not fully understand why we have to square the $C_{h-1}$ – Christian Singer Jun 3 at 9:13
• Each heap of height $h$ consists of a root together with two heaps of height $h-1$. – Yuval Filmus Jun 3 at 9:21
• 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 – Christian Singer Jun 3 at 9:31

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.

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