wu :: forums « wu :: forums - Probabiilty of a Heap » Welcome, Guest. Please Login or Register. Jan 14th, 2025, 8:50pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: william wu, Icarus, ThudnBlunder, Grimbal, Eigenray, towr, SMQ)    Probabiilty of a Heap « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Probabiilty of a Heap  (Read 773 times) howard roark Full Member     Posts: 241 Probabiilty of a Heap   « on: Jan 28th, 2009, 5:26pm » Quote 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: Posts: 919 Re: Probabiilty of a Heap   « Reply #1 on: Jan 28th, 2009, 10:45pm » Quote 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 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: Posts: 13730 Re: Probabiilty of a Heap   « Reply #3 on: Jan 29th, 2009, 2:07am » Quote 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 Modify towr could you explain how did he calculate number of heaps? IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: Probabiilty of a Heap   « Reply #5 on: Jan 30th, 2009, 10:34pm » Quote 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 Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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