GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
194 views
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
asked in Programming by Veteran (12.2k points)   | 194 views
should'nt it be 4??
given is 8 , m getting 9

2 Answers

+7 votes
Best answer
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.
answered by Veteran (23.5k points)  
selected by
when 4 is 2nd node then 1,2,3 any can be any leaf right ..you missed that cases rt
@vijaycs SIR is there any mathematical approch for the same question ? Like say if n nodes are to be inserted

@vijay

what if an array of 100 elements given?
cant always go with hit n trail...there should be a generalised way keeping in mind height factor and how many will be in left subtree and how many in right
Ans 8,rt?

how 9?@Sonam

@sudsho

Yes, what if 100 elements ?

https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements

This shows some generalization but I have never applied it. Should we try ?

i did with permutation which you considered but writing all cases ,..  but it will take time and if you miss any case then it will give wrong ans ,

i did like first fix 5 as root( 1 way) then , at 2nd level 3,4 node so there 2 cases

1) when 3 is 2nd node then 3rd node fixed 4 and other 2 nodes either 1,2 (2 ways)

2) when 4 is 2nd node then remainning nodes will pe arrange in 3! way = 6 ways

so total 6+2+1 =9 , yes ans is 8 but where i am leaking ?
yes , given soln is same in test series.
5 fixed not a case here.

until we go upto leaf , we cannot consider a way.
Ok... :) Keep in mind
+2 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
answered by Veteran (12k points)  
Thanks
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users