The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes
A level of a max heap (containing 100 nos) is choosen randomly, on its selection, a node from the same level is choosen randomly. What is the probability that it is the 36th  smallest element
asked in Algorithms by Junior (965 points)
reshown by | 385 views
0.087 ?
0.0038 ?
There will be 7 levels in a max heap with 100 elements.  The 36th smallest element will be in the last level (with 37 elements), also it could be either of these 37 elements

So the probabilty that we choose 36th smallest element will be

1/7 * 1/37 = 1/259 = 0.0038

Correct me if I am wrong
where is this question taken from ?

i too did the same thing but debashish got a diff answer.
if numbers are from 1-100 (inclusive) then '36' can be in 2nd level.
I haven't taken it from any where kinda thought of it by myself
I am not sure about my answer, although
debashish please explain your approach ,if 36 is in 2nd level then atlast the resultant tree willn't be complete binary tree thus it's not a heap ..??
In the heap : right subtree contains 36 elements, left subtree contains 63 elements. If we assign number 36 to the right child of the root,  then remaining 35 numbers in the right subtree can be filled up using [1,35]. Please mention if anything wrong !

And further , if numbers are in between [1,100], then '36' can be at any level from 2 to 7. (not at the same time of course)
yes,  u r correct ..then we can calculate like  1 / 6   (2nd level prob + 3rd level prob + 4th level prob + 5th level prob + 6th level prob) i.e., we can chose either from 2nd level or 3rd level or 4th or 5th or 6th , is it correct ??
what I did is

P = $\frac{1}{7}*0 + \frac{1}{7}*\frac{1}{2} + \frac{1}{7}*\frac{1}{4} + \frac{1}{7}*\frac{1}{8}+ \frac{1}{7}*\frac{1}{16}+ \frac{1}{7}*\frac{1}{32}+ \frac{1}{7}*\frac{1}{37} = 0.087$

Suggestion and correction plz !
@Debashish Deka u r correct...

having one dout ... 36 at level 2 is at fixed location at right end and having only one u takes probability=1/2 since this level having 2 ele.

now at level 3 having 4 elements ...but at this level 36 can be at any place ... u takes probability=1/4 here having 4 choices...

confusing probability for me! plz explain !
@Debashish , why 36 occurs in any level from 2 to 7.
@debashish, can you make that an answer

1 Answer

0 votes
Its P(65th largest element given that a level is chsen and an elemwnt is chosen from it)

So P= ((1/7)*(1/37))/((1/7)+(1/7)*(1/2)+......+ (1/7)*(1/2^5)+(1/7)*(1/37))

answered by (421 points)

Related questions

0 votes
0 answers
asked in Algorithms by vivek9837 Junior (965 points) | 53 views
0 votes
0 answers
asked in Algorithms by Anjana Babu Active (1.3k points) | 201 views

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

29,017 questions
36,844 answers
34,721 users