Heap

Author

Eric W. Weisstein
September 14, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/ComputerScience/Heap.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Heap.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<Combinatorica`

Code

HeapQ[a_List?PermutationQ]:=Module[{i,n=Length[a]},
And@@Table[a[[Floor[i/2]]]<a[[i]],{i,2,n}]
]

Heapification

RandomPermutation[10]

Heapify[%]

ShowLabeledGraph[CompleteBinaryTree[10],{1,2,3,8,5,7,4,9,10,6}]

Show[GraphicsArray[{
Show[ShowLabeledGraph[CompleteBinaryTree[10],{1,2,3,8,5,7,4,9,10,6}],PlotRange->All,AspectRatio->.5],
Show[ShowLabeledGraph[CompleteBinaryTree[30],Heapify[RandomPermutation[30]]],AspectRatio->.5,PlotRange->All]
}]]

Counts

S[1]:=1
S[l_]:=Binomial[2^l-2,2^(l-1)-1]S[l-1]^2

Table[S[i],{i,5}]

RSolve[{S[l]==Binomial[2^l-2,2^(l-1)-1]S[l-1]^2,S[1]==1},S[l],l]

Table[(E^((2^(-1+l)) (∑_(K[1]=0)^(-1+l))(2^(-K[1])) Log[Binomial[-2+(2^(1+K[1])),-1+(2^(K[1]))]])),{l,0,5}]//Simplify

Table[Product[2

((((2^n)-1)!)/(Product[((((2^k)-1))^(2^(n-k))),{k,n}]))

Table[Product[((((2^k)-1))^(2^(n-k))),{k,n}],{n,5}]

l=Table[((((2^n)-1)!)/(Product[((((2^k)-1))^(2^(n-k))),{k,n}])),{n,0,8}]

FindSequenceFunction[%]

FindGeneratingFunction[l,n]

n Elements

Table[Count[Permutations[Range[n]],_?HeapQ],{n,8}]

Table[Count[Permutations[Range[n]],_?HeapQ],{n,9,10}]

Table[Select[Permutations[Range[n]],HeapQ],{n,5}]//ColumnForm

Of Level n

Select[Permutations[Range[2^3-1]],HeapQ]

Length[%]

Table[2^l-1,{l,5}]

Heaps on n Elements

s[0]:=1
s[1]:=1
 s[n_]:=s[n]=Module[{h=Floor[Log[2,n+1]]-1,b,r,r1,r2},
b=2^h-1;
r=n-1-2b;
r1=r-Floor[r/2^h](r-2^h);
r2=r-r1;
Binomial[n-1,b+r1]s[b+r1]s[b+r2]
]

s/@Range[20]

Heaps on l Levels

s[1]:=1
s[l_]:=s[l]:=Binomial[2^l-2,2^(l-1)-1]s[l-1]^2

RSolve[{s[l]==Binomial[2^l-2,2^(l-1)-1]s[l-1]^2,s[1]==1},s[l],l]

Table[s[l],{l,5}]