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

@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