# Number of possible min heaps

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is --------------

According to me, the answer should be 48. The first element 1 is fixed as root. The next level contains elements 2 and 3. The third level contains 4,5,6,7. Therefore, the total no. of cases should be 4! * 2!=48.

But my solution manual says that the answer should be 80.

Am I correct? If not, what am I doing wrong?

The second level can contain other numbers than 2 and 3. See for example

      1
/ \
2   5
/ \
3   7
/ \
4   6


It is also unclear if you count isomorphic trees. See this question for a related answer.

• Hi @A.Schulz, your tree is not a min heap. The 1st level is not filled up. Please correct me if I am wrong. – Abhilash Mishra Mar 7 at 17:10
• @AbhilashMishra A min-heap can be unbalanced. – Apass.Jack Mar 7 at 20:22
• Hi @A.Schulz, can you please cite a source for me to read about min-heaps and their properties. Please provide a link where I can know more about unbalanced min-heaps. It seems I am missing a very crucial point in min-heaps. Thanks a lot for your help. – Abhilash Mishra Mar 8 at 5:01
• Any cs textbook on data structures will do the job. For example Cormen et al. – A.Schulz Mar 8 at 14:20