The behaviour of three methods for constructing a binary heap on
a computer with a hierarchical memory is
studied. The methods considered are the original one proposed by
Williams [1964], in which elements are repeatedly inserted into a
single heap; the improvement by Floyd [1964], in which small heaps are
repeatedly merged to bigger heaps; and a recent method proposed,
e. g., by Fadel et al. [1999] in which a heap is built layerwise.
Both the worst-case number of instructions and that of cache misses
are analysed. It is well-known that Floyd’s method has the best
instruction count. Let *N* denote the size of the heap to be
constructed, *B* the number of elements that fit into a cache line,
and let *c* and *d* be some positive constants. Our analysis shows
that, under reasonable assumptions, repeated insertion and layerwise
construction both incur at most *c* *N* / *B* cache misses, whereas repeated
merging, as programmed by Floyd, can incur more than (*d* *N* log_{2}
*B*) / *B* cache misses. However, for our memory-tuned versions of repeated
insertion and repeated
merging the number of cache misses incurred is close to the optimal
bound *N* / *B*.
In addition to these theoretical findings, we communicate many practical
experiences which we hope to be valuable for others doing experimental
algorithmic work. |