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).
