Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How many different max-heaps can I form using a list of $n$ integers.

Example: list [1,2,3,4]

and max-heap is 4 3 2 1 or

   / \
  3   2

other possible max-heap is 4 2 3 1

   / \
  2   3 
share|cite|improve this question
up vote 16 down vote accepted

I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...

You can find a not-so-nice recursion in the OEIS database. Basically the idea is as follows. The root of an $n$-ary heap is always the maximum. The two subtrees hanging off the root are again maxheaps. Their size depends on $n$, is a bit tedious to compute the sizes $n_1,n_2$ (see the OEIS entry), clearly $n_1+n_2=n-1$. We can now pick, which elements go to the left heap and which go to the right heap. There are ${n-1 \choose n_1}$ ways how to distribute the elements. This gives the recurrence

$$ a(n)= {n-1 \choose n_1} a(n_1)a(n_2).$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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