wu :: forums
« wu :: forums - Probabiilty of a Heap »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 10:14pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Eigenray, SMQ, Grimbal, ThudnBlunder, william wu, towr, Icarus)
   Probabiilty of a Heap
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Probabiilty of a Heap  (Read 764 times)
howard roark
Full Member
***





   


Posts: 241
Probabiilty of a Heap  
« on: Jan 28th, 2009, 5:26pm »
Quote Quote Modify Modify

Given an array (of n elements) what is the probability of array being a heap?
 
Assume we are dealing with Max Heap: Parent is greater than both of its children
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Probabiilty of a Heap  
« Reply #1 on: Jan 28th, 2009, 10:45pm »
Quote Quote Modify Modify

I suppose you mean binary heap with implicit edges i2i+1,i2i+2.
IP Logged
howard roark
Full Member
***





   


Posts: 241
Re: Probabiilty of a Heap  
« Reply #2 on: Jan 28th, 2009, 10:59pm »
Quote Quote Modify Modify

Exactly....
 
Quote:
I suppose you mean binary heap with implicit edges i2i+1,i2i+2.
« Last Edit: Jan 28th, 2009, 11:00pm by howard roark » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Probabiilty of a Heap  
« Reply #3 on: Jan 29th, 2009, 2:07am »
Quote Quote Modify Modify

A056971 divided by A000142
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
howard roark
Full Member
***





   


Posts: 241
Re: Probabiilty of a Heap  
« Reply #4 on: Jan 30th, 2009, 4:06pm »
Quote Quote Modify Modify

towr could you explain how did he calculate number of heaps?
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Probabiilty of a Heap  
« Reply #5 on: Jan 30th, 2009, 10:34pm »
Quote Quote Modify Modify

A heap on [1,n] has h complete levels, plus an extra r nodes on the last level, when n = 2h-1 + r, with 1 r 2h.
 
If r 2h-1, then the right child of the root is a complete heap with 2h-1 - 1 nodes, and the left child therefore has n - 2h-1 nodes.  Otherwise, the left child of the root has 2h -1 nodes, and the right has n - 2h.
 
Now, to make a heap on [1,n], the root node must be n.  Then we pick which values go on the left and which go on the right, and then recursively make heaps out of both sets.  (Note that the number of heaps using a given set of distinct values only depends on the size of the set.)
 
So, if f(n) is the number of heaps on [1,n], then f(0) = f(1) = 1, and  
 
f(n) = C(n-1, 2h-1-1) f(2h-1-1) f(n-2h-1), if r 2h-1,
f(n) = C(n-1, 2h-1) f(2h-1) f(n-2h), if r > 2h-1.
 
This is equivalent to the given formula.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board