3,969 views
9 votes
9 votes
The number of ways , in which numbers 1,2,3,4,5 can be inserted into binary heap,such that resultant binary heap is max heap ?

given ans :8

2 Answers

Best answer
10 votes
10 votes
Yes, It is 8. [ Thanks @Kapil , @Sonam :) ]  

1. 5, 4, 3, 2, 1

2. 5, 4, 3, 1, 2

3. 5, 3, 4, 2, 1

4. 5, 3, 4, 1, 2

5. 5, 4, 1, 2, 3

6. 5, 4, 1, 3, 2

7. 5, 4, 2, 3, 1

8. 5, 4, 2, 1, 3.
selected by
3 votes
3 votes
Answer wil be 8 only . First th will be fixed to the root .

Now it is difficult to see from the internal nodes see from leaves. The remaining elements are (1,2,3,4). There will be 2 leaves possible. So possible pairs will be .

if we choose (1,2) in leafs then the possiblity for its root is (3 or 4) . So 2 choices for root and 1,2 can also be arranged in 2 ways - total choices = 2*2 = 4
like wise

(1,3) - 1 choice i.e 4. but arrangement of 1,3 or 3,1 possible - 2*1 choices - 2

(1,4 ) not possible

(2,3) - 1 choice = 1*2 = 2 choices

(2,4) not possible

(3,4) not possible

total ways = 4+2+2 = 8 choices

Related questions

2 votes
2 votes
1 answer
1
Thor-o-s asked Sep 1, 2022
391 views
Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinctPlease use max heap to explain the working input : n distinct e...
2 votes
2 votes
0 answers
2
Markzuck asked Jan 13, 2019
1,202 views
Please explain the logic behind this shortcut and when to be used?