Max heap

Question

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

Comments

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 choice..here 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

Answer 1

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))

P=0.0135

Answer 2

According to me, 36 can be present at any level except @0^th, hence

p= probablity of choosing 36^th  smallest element provided any level is choosen

p= 1/7∗(1/2+1/4+1/8+1/16+1/32+1/37)  

p= 0.1422