min heap

Question

The number of binary min. heaps that can be formed from a set of 7 distinct integers is _________?

Comments

Same question asked in 2018

---

What is the source of this question?
Because the same was asked in GATE 2019.

---

https://youtu.be/1U3loHkX5XE?t=2119  Watch from 35:15

Answer 1

• Pick any $7$ distinct  integers and sort it .
• After sorting, pick the minimum element and make it the root of the min heap. So, there is only $1$ way to make the root of the min heap.
• Now we are left with $6$ elements.
• Total ways to design a min heap from $6$ elements = $C(6,3) * 2! * C(3,3) * 2!$ = $80$ 

---

$C(6,3) * 2!$ :- Pick up any $3$ elements for the left subtree and each left subtree combination can be permuted in $2!$ ways by interchanging the children and similarly, for right subtree .

---

---

How many min heaps for $N = 15$ elements ?

• Pick any $15$ distinct  integers and sort it .
• After sorting, pick the minimum element and make it the root of the min heap. So, there is only $1$ way to make the root of the min heap.
• Now we are left with $14$ elements.
• Total ways to design a min heap from $14$ elements 

=> $C(14,7) * \left ( C(6,3) * 2! * C(3,3) * 2! \right ) * C(7,7) * \left ( C(6,3) * 2! * C(3,3) * 2! \right )$

---

$C(14,7) * \left ( C(6,3) * 2! * C(3,3) * 2! \right )$ :- Pick up any $7$ elements for the left subtree and fix the root. Now, we are left with $6$ elements and using the same procedure for above problem, take each left subtree combination can be permuted in $2!$ ways by interchanging the children and similarly, for right subtree .

Comments

here we are using this because

C(14,7)∗(C(6,3)∗C(2,1)∗C(3,3)∗C(2,1))∗C(7,7)∗(C(6,3)∗C(2,1)∗C(3,3)∗C(2,1))

here 2!=2C1   means we are choosing one key from two and assign it as left key and remaining one will be right

---

Best solution ever. Thank you

---

Well, same logic. Basic idea is to design a complete binary tree and everything will be the same .

 

Please explain it further by taking an example.

Answer 2

Here i m generalizing it with an  example....
suppose i have a min heap like this

assume root at level zero hight of this heap is k=3 
The smallest element has to be placed at the root of the heap.  After that we split up the remaining elements into the two subtrees and recursively compute the number of binary heaps that they can make.  The trickiest part here is that the two subtrees don't have necessarily have the same number of nodes (unless N is 1 less than a power of two).

We fill the tree in breadth first order which means that nodes in the lowest level will go to the left subtree first and then any excess nodes will be in the right subtree.
suppose that at last level there r m nodes nd total nodes=n
                        hence n=2^k-1 +m
in above tree k=3 m=7 so n=2^k-1 +m=8-1+7=14
    or we can say that m=n-2^k+1
now calculate number of elements in the left subtree as L ?
we now that before last level every level is complete and nodes r equally distributed into left subtree nd .right subtree.
so no of nodes befor last level in  left subtree or.right subtree.=p 
    now we know that befor last level total nodes=2^k-1 now leave root now total nodes=2^k-2
these total nodes 2^k-2, is equally distributed into left subtree nd .right subtree.
hence p=(2^k-2)/2=2^k-1 -1
now suppose number of elements in the left subtree as L and number of elements in the right subtree as L
L=p+min(2^k-1,m )        R=p+max(0,m-2^k-1)
expalanation for  L=p+min(2^k-1,m )        R=p+max(0,m-2^k-1)
For L=p+min(2^k-1,m )        R=p+max(0,m-2^k-1) 
there r 2 cases 
case-1 
if our lst part is not complete then it ll surely have m elements in left sub tre part=no of nodes at last level so if all nodes at last level comes in lst part so there r o nodes in rst part it gives 
     L=p+min(   ,m )        R=p+max(0,   ) 
case 2  
if our lst part is  complete nd there r some nodes also in rst part 
so for lst part 2^k/2=2^k-1 nodes in lst part at last level nd rest nodes out of m ie m-2^k-1 will be on rst part at last level 
               L=p+min(2^k-1,    )        R=p+max(   ,m-2^k-1) 
 now by cobining case 1&2 
L=p+min(2^k-1,m )        R=p+max(0,m-2^k-1)

Returning to the original problem you can calculate f(n), the number of binary heaps with n distinct elements, as f(n)
f(0)=1, f(1)=1
f(n)=n-1C_Lf(L)f(R)
this is generating series (1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600)
http://oeis.org/A056971
f(7)=80
          p.s.  https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements

----------------------------------------------------------------------------------------------------------------------------------------------------------------
if we have our min heap as complete binary tree then this method makes it mor simpler bcoz for a complete binary tree for every node its left sub tree nd right sub tree  is also complete binary tree with same no of nodes in lst and rst  nd they have also same no of binary min heaps means f(L)=f(R)
    suppose n=15 means it is complete as 2⁴-1=15, k=3
L=R=2^k-1=7 
f(15)=14c₇ *(f(7))²
f(7)=6c₃*(f(3))²
f(3)=2c₁*(f(1))²
f(1)=1

Comments

For L=p+min(2^k-1,m )        R=p+max(0,m-2^k-1)
there r 2 cases
case-1
if our lst part is not complete then it ll surely have m elements in left sub tre part=no of nodes at last level so if all nodes at last level comes in lst part so there r o nodes in rst part it gives
     L=p+min(   ,m )        R=p+max(0,   )
case 2 
if our lst part is  complete nd there r some nodes also in rst part
so for lst part 2^k/2=2^k-1 nodes in lst part at last level nd rest nodes out of m ie m-2^k-1 will be on rst part at last level
               L=p+min(2^k-1,    )        R=p+max(   ,m-2^k-1)
 now by cobining case 1&2
L=p+min(2^k-1,m )        R=p+max(0,m-2^k-1)

---

how f(0) = 1?

---

great!

Answer 3

Ans is 80

As the smallest element will be at root and for left sub tree from remaining 6 element we can pick any six element 6C3 and smallest element among 3 will be root and remaining element we can arrange by 2!

Similarly for right subtree 3C3*2!

So 6C3*2!*3C3*2!=80

Comments

Thanks for the amazing explanation

Answer 4

                      

Therefore total choice = 2*5*4=40

Same can be done on right subtree of root.

So there are total = 40 * 2 choices =80 Ans

Comments

In 2nd level

{2,3} is not only choice

it could be {2,3} or {2,4} or {2,5}

right?

---

No I dnt think 2nd level can store 4 or 5 otherwise it will violate min-heap property.

As  i can have

             

---

COUNTER EXAMPLE IS :-

LEVEL 0 : -                  1

LEVEL 1 :-            4            2

lEVEL 2 :-         5      7      3        6