A heap structure designed for secondary storage is suggested that
tries to make the best use of the available buffer space in primary
memory. The heap is a complete multi-way tree, with multi-page blocks
of records as nodes, satisfying a generalized heap property. A special
feature of the tree is that the nodes may be partially filled, as in
B-trees. The structure is complemented with priority-queue operations
insert and delete-max. When handling a sequence of *S* operations,
the number of page transfers performed is shown to be
*O*(∑_{i=1}^{S}(1 / *P*) log_{(M / P)}
(*N*_{i} / *P*)), where *P* denotes the number of records
fitting into a page, *M* the capacity of the buffer space in records,
and *N*_{i} the number of records in the heap prior to the *i*th
operation (assuming *P* ≥ 1 and *S* > *M* ≥ *c*· *P*, where *c* is
a small positive constant). The number of comparisons required when
handling the sequence is *O*(∑_{i=1}^{S}log_{2} *N*_{i}).
Using the suggested data structure we obtain an optimal external
heapsort that performs *O*((*N* / *P*) log_{(M / P)}
(*N* / *P*)) page transfers and *O*(*N* log_{2} *N*)
comparisons in the worst case when sorting *N* records. |