0
$\begingroup$

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?

Thanks in advance

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi @A.Schulz, your tree is not a min heap. The 1st level is not filled up. Please correct me if I am wrong. $\endgroup$ – Abhilash Mishra Mar 7 at 17:10
  • 1
    $\begingroup$ @AbhilashMishra A min-heap can be unbalanced. $\endgroup$ – Apass.Jack Mar 7 at 20:22
  • $\begingroup$ 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. $\endgroup$ – Abhilash Mishra Mar 8 at 5:01
  • 1
    $\begingroup$ Any cs textbook on data structures will do the job. For example Cormen et al. $\endgroup$ – A.Schulz Mar 8 at 14:20

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.