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$
6
  • $\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 '19 at 17:10
  • 1
    $\begingroup$ @AbhilashMishra A min-heap can be unbalanced. $\endgroup$ – John L. Mar 7 '19 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 '19 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 '19 at 14:20
  • $\begingroup$ @A.Schulz; I think the example in your answer is not a heap. In the book "Introduction to Algorithms" by Cormen and others, one of the properties of a binary is heap is that they are complete at all levels except possible the lowest level. $\endgroup$ – Ramasamy Kandasamy Apr 14 at 14:11
2
$\begingroup$

The flaw in your approach is that you assume that the second level contains only $2$ and $3$. The following examples is min heap with $3$ not in the second level.

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

The solution is available here.

Solution: The root of the tree has to be the minimum element, therefore $1$ is at the root.

Now we need to find the possible ways to fill the left and right subtrees with the remaining $6$ elements. Each of the subtrees contain three elements. For the left subtree we can choose $3$ elements from $6$ elements in $\binom{6}{3}$ ways and the remaining three elements fill the right subtree.

Now in each of these subtrees the root would be the minimum of the three elements that comprise each of these subtrees. However, the two lowest elements in each of these subtrees can be interchanged. Therefore each of the subtrees can exists in two different configurations.

Therefore the total possible configurations would be:

$\binom{6}{3} \times 2 \times 2 = 80$.

$\endgroup$

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.