A binary heap in the minimum-heap convention is a sequence 
satisfying 
for 
, where 
is the floor function,
which is equivalent to 
for 
and 
for 
. The first
member must therefore be the smallest. A heap can be viewed as a labeled complete
binary tree in which the label of each node is
no greater than the labels of its descendants (Skiena 1990, p. 35). A heap with
elements supports arbitrary insertion
and deletion of the minimum value in 
time per update (Skiena 1990, p. 38). Here, big-O
notation 
means that the running time is at most a fixed positive multiple of 
once 
is sufficiently large.
The minimum can be read in 
time. An algorithm due to
Floyd (1964) builds a heap from a list of 
elements in 
time, meaning that the running time grows at most linearly
with the length of the list. 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, ... distinct ordered labels 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)
|
for 
, with 
, where 
, 
, 
, 
,
and 
.
The number of heaps with 
fully occupied levels, or equivalently 
elements, is given by the recurrence
relation
 |
(2)
|
for integer 
, with 
(Skiena 1990, p. 36). This can be written as a product as
 |
(3)
|
the values of which for 
, 2, ... are 1, 2, 80, 21964800,
74836825861835980800000, ... (OEIS A056972).
