Heap

A sequence {a_n}_(n=1)^N forms a (binary) heap if it satisfies a_(|_j/2_|)<=a_j for 2<=j<=N, where |_x_| is the floor function, which is equivalent to a_i<a_(2i) and a_i<a_(2i+1) for 1<=i<=(N-1)/2. The first member must therefore be the smallest. A heap can be viewed as a labeled binary tree in which the label of the ith node is smaller than the labels of any of its descendents (Skiena 1990, p. 35). Heaps support arbitrary insertion and seeking/deletion of the minimum value in O(lnn) times per update (Skiena 1990, p. 38).

A list can be converted to a heap in O(n) times using an algorithm due to Floyd (1964). For example, given the random permutation {6,2,7,9,5,3,4,8,10,1}, Floyd's algorithm gives the heap {1,2,3,8,5,7,4,9,10,6} (left figure). The right figure shows a heap containing 30 elements.

The numbers of heaps a(n) on n=1, 2, ... elements are 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, ... (OEIS A056971), the first few of which are summarized in the above table. A formula for a(n) is given by

with a(0)=0, a(1)=1, and

The number of heaps of l levels (or equivalently, the number of heaps of 2^l-1 elements) is given by the recurrence relation

with S_1=1 (Skiena 1990, p. 36). This can be written as a product as

the values of which for l=1, 2, ... are 1, 2, 80, 21964800, 74836825861835980800000, ... (OEIS A056972).

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Heap." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Heap.html

Subject classifications