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 ith 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^Slog₂ 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₂ N) comparisons in the worst case when sorting N records.

@article{FJKT1999J,
  author = {R. Fadel and K. V. Jakobsen and J. Katajainen and J. Teuhola},
  title = {Heaps and heapsort on secondary storage},
  journaltitle = {Theoretical Computer Science},
  volume = {220},
  number = {2},
  year = {1999},
  pages = {345--362},
}