GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
600 views
The number of binary min. heaps that can be formed from a set of 7 distinct integers is _________?
asked in DS by Active (2.1k points) 3 16 51 | 600 views
@saurabh SIR,
Can u ps make an answer ?  I didnt understand the link :(
ok dont worry..... in which part u r facing problem tell me i ll explain u surely.....
I only undrstood upto filling them in breadfirst manner .   What we have to do after that ?  How did he got the equation ? Could u able to explain it in simple words taking this example . ?
ok....
waiting :)
48 ans??
I did like this.

The height of the heap is 2.

Since it is a minheap, so root has only one choice ie the minimum element.

At height 2, we have the 4 maximum elements, which have 4! possibilities.

At height 1, we have remaining 2 elements, which can be arranged in 2! ways.

So, 4! * 2! = 48 min heaps.
No, Its not the answer.

There are more possibilities: Suppose elements are (1234567)

level 1 -     1

level 2 -   2, 5    

level 3 -  3,4  6,7

(u have choose only 2 and 3 in level 2)
aPPROACH GIVEN IN ABOVE LINK IS DIFFERENT FROM YOURS RIGHT ?

Why have you multiplied 4! * 2 !  didnt understand this part in ur explanation
answer given is 80 donno how even i got 48
Yes @target2017

There are more possibilities.
@gateset @jithin see my ans bellow....
yes I got it thank u so much great explanation :)

2 Answers

+19 votes
Best answer
  • 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 .

answered by Veteran (50.4k points) 22 90 410
selected by
Any signififance of C(6,3) in general case ?

ie in n = N  then
C((N-1) , (N-1)/2 ) * 2!  * C((N-1)/2 , (N-1)/2 )   when n is odd  . Can i generalize like this ?
Yes, some generalization is there . I've edited. You can check now !!
What if N is EVEN ?
Well, same logic. Basic idea is to design a complete binary tree and everything will be the same .

for n=7

for n=8

Right @pC :)
How do you calculate for n=5 @Kapil Veteran
Can you try and tell me ? Logic above remains the same .
Yes,got it.initially i thought that i should divide the n-1 integers into two halves,but later i found out the property of heap.So,i got it now.Answer was great but it would be more helpful if you have also added how to divide n-1 integers into L and R.Thanks again for the answer :)

for n=5

n-1=4

here by heap property L=3 and R=1

So,f(5)=4C3 * f(3) * f(1)
+8 votes

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=2k-1 +m
in above tree k=3 m=7 so n=2k-1 +m=8-1+7=14
    or we can say that m=n-2k+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=2k-1 now leave root now total nodes=2k-2
these total nodes 2k-2, is equally distributed into left subtree nd .right subtree.
hence p=(2k-2)/2=2k-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(2k-1,m )        R=p+max(0,m-2k-1)
expalanation for  L=p+min(2k-1,m )        R=p+max(0,m-2k-1)
For L=p+min(2k-1,m )        R=p+max(0,m-2k-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 2k/2=2k-1 nodes in lst part at last level nd rest nodes out of m ie m-2k-1 will be on rst part at last level 
               L=p+min(2k-1,    )        R=p+max(   ,m-2k-1
 now by cobining case 1&2 
L=p+min(2k-1,m )        R=p+max(0,m-2k-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-1CLf(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 24-1=15, k=3
L=R=2k-1=7 
f(15)=14c7 *(f(7))2
f(7)=6c3*(f(3))2
f(3)=2c1*(f(1))2
f(1)=1

answered by Veteran (11.8k points) 13 42 139
edited by
Thank you so much :)
if u have little bit doubt also u can ask
btw i m nt sir.... :)

How you got
 L=p+min(2k-1,m )        R=p+max(0,m-2k-1)

Equation ?

I understood upto p=(2k-2)/2=2k-1 -1 statement .

You could have explained it using the same example till the last  instead of that series . The traditional way just to understand this topic 
This is such a nice explanation.

Thanks :)

For L=p+min(2k-1,m )        R=p+max(0,m-2k-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 2k/2=2k-1 nodes in lst part at last level nd rest nodes out of m ie m-2k-1 will be on rst part at last level
               L=p+min(2k-1,    )        R=p+max(   ,m-2k-1)
 now by cobining case 1&2
L=p+min(2k-1,m )        R=p+max(0,m-2k-1)

how f(0) = 1?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23338 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7912 Points

  4. srestha

    6228 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question makhdoom ghaya
Popular Question junaid ahmad
Notable Question learner_geek
Notable Question jothee
Popular Question jothee
Notable Question Jeffrey Jose
Notable Question air1ankit
Nice Question jothee
Verified Human shaleen25
Popular Question jothee
27,290 questions
35,142 answers
83,920 comments
33,231 users