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
