Algorithm_heap

Question

The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into
a Binary Heap such that resulted binary heap is Max Heap.
Please  give the ans and what is the formula for n distinct elements?

Comments

@tariq husain khan plz tell me which resource or test series is that question

Answer 1

Given inputs that can be inserted in the heap$H= \left \{ 1,2,3,4,5 \right \}$ and the resultant heap must be a max heap.

$\Rightarrow 5 must$ be root(No Choice) and we are left with 4 element.

$\Rightarrow$we have now two sets one is Left Subtree (let it be 'L') and other is Right Subtree(let it be 'R')

$\Rightarrow \left | L \right |=3 and \left | R \right |=1$  (Reason-:Heap is complete/almost complete binary tree)

The two sets look like$\Rightarrow$

S_N_O	Set L	Set R
1	$\left \{ 1,2,3 \right \}$	$\left \{ 4 \right \}$
2	$\left \{ 2,3,4 \right \}$	$\left \{ 1 \right \}$
3	$\left \{ 1,3,4 \right \}$	$\left \{ 2 \right \}$
4	$\left \{ 1,2,4 \right \}$	$\left \{ 3 \right \}$

For S_N_O 1$\Rightarrow$ 3 must be root and '1' and '2' is left or right child (2 choices for S_N_O 1) and same for all the S_N_O .. so total possiblity=2+2+2+2=8 

Answer 2

Ans should be 4.

Comments

no

Answer should be 8

5 is fixed at root

1st way: we can have(1,2,3) in LST and only 4 at the RST : here (1,2,3) can be arranged in 2 ways by keeping 3 as root in LST

2nd way :(1,2,4) at LST which itself can be done in 2 ways and keep 3 at RST

3rd way: (1,3,4) at LST and 2 at RST

4th way : (2,3,4) at LST and 1 at RST

total ways = 2*2*2*2 = 8 ways

LST and RST are left subtree and right subtree

---

Yes , i got it ans is 8 .Your algo is correct except in line of 1st way 2 cant be the root of LST it should be 3 bcoz it violates the max heap property.

---

@cse23 There is a slight mistake in the solution you provided.

1st way : (1,2,3) in the LST can be arranged in only one way coz. in order to maintain a Max-Heap u can only choose 3 as root which is the largest of the three.

Similarly for 2nd way, 3rd way and 4th way you can only choose 4 as root to maintain the heap property.

Hence in total there are 4 ways.

---

@Sourav It is correct that only 4 can be chosen as root, but children of 4 can be arranged in 2 ways again. So this gives total 8 ways.

And for generic formula please refer : https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements

---

@Kantikumar thnx for pointing this, i got it now.

---

@sourav

thanks for pointing..corrected now.

Yes, It will be 8 ways.