We examine three quantities related to heaps: the number of heaps with
n nodes, the number of permutations generating the same heap, and the
average number of exchange operations necessary for generating a heap
from a given permutation. We find recurrence relations for these quan
tities, and are thus able to compute them in time O(ln n). We also obt
ain the asymptotic values for n = 2(r) - 1. We determine an upper and
a lower bound for the number of exchange operations involved (a well-k
nown quantity in computer science), and study its behavior when n rang
es between two consecutive powers of 2.