A sequence forms a (binary) heap if it satisfies for , where is the floor function, which is equivalent to and for . The first member must therefore be the smallest. A heap can be viewed as a labeled binary tree in which the label of the th 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 times per update (Skiena 1990, p. 38).
A list can be converted to a heap in times using an algorithm due to Floyd (1964). For example, given the random permutation , Floyd's algorithm gives the heap (left figure). The right figure shows a heap containing 30 elements.
heaps | |
1 | 1 |
2 | 1, 2 |
3 | 1, 2, 3, 1, 3, 2 |
4 | 1, 2, 3, 4, 1, 2, 4, 3, 1, 3, 2, 4 |
The numbers of heaps on , 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 is given by
(1)
|
with , , and
(2)
| |||
(3)
| |||
(4)
| |||
(5)
| |||
(6)
|
The number of heaps of levels (or equivalently, the number of heaps of elements) is given by the recurrence relation
(7)
|
with (Skiena 1990, p. 36). This can be written as a product as
(8)
|
the values of which for , 2, ... are 1, 2, 80, 21964800, 74836825861835980800000, ... (OEIS A056972).