wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Probabiilty of a Heap
        
(Message started by: howard roark on Jan 28^th, 2009, 5:26pm)

Title: Probabiilty of a Heap
Post by howard roark on Jan 28^th, 2009, 5:26pm

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

Title: Re: Probabiilty of a Heap
Post by Hippo on Jan 28^th, 2009, 10:45pm

I suppose you mean binary heap with implicit edges ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif2i+1,ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif2i+2.

Title: Re: Probabiilty of a Heap
Post by howard roark on Jan 28^th, 2009, 10:59pm

Exactly....

Quote:

I suppose you mean binary heap with implicit edges i2i+1,i2i+2.

Title: Re: Probabiilty of a Heap
Post by towr on Jan 29^th, 2009, 2:07am

A056971 (http://www.research.att.com/~njas/sequences/A056971) divided by A000142 (http://www.research.att.com/~njas/sequences/A000142)

Title: Re: Probabiilty of a Heap
Post by howard roark on Jan 30^th, 2009, 4:06pm

towr could you explain how did he calculate number of heaps?

Title: Re: Probabiilty of a Heap
Post by Eigenray on Jan 30^th, 2009, 10:34pm

A heap on [1,n] has h complete levels, plus an extra r nodes on the last level, when n = 2^h-1 + r, with 1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2^h.

If r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2^h-1, then the right child of the root is a complete heap with 2^h-1 - 1 nodes, and the left child therefore has n - 2^h-1 nodes. Otherwise, the left child of the root has 2^h -1 nodes, and the right has n - 2^h.

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, 2^h-1-1) f(2^h-1-1) f(n-2^h-1), if r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2^h-1,
f(n) = C(n-1, 2^h-1) f(2^h-1) f(n-2^h), if r > 2^h-1.

This is equivalent to the given formula.