Heaps and heapsort on secondary storage
Authors:R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola
Published in:Theoretical Computer Science 220,2 (1999), 345-362
Full text:<pdf.gif>PDF (199 kB)  <ps.gif>PS (439 kB)  
Copyright:© Elsevier Science B.V.

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=1S(1 / P) log(M / P) (Ni / P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and Ni the number of records in the heap prior to the ith operation (assuming P ≥ 1 and S > Mc· P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑i=1Slog2 Ni). 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 log2 N) comparisons in the worst case when sorting N records.

Related:<html.gif>HTML (Technical report)  <html.gif>HTML (Conference paper)  
  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},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.