External heaps combined with effective buffering
Authors:Ramzi Fadel, Kim Vagn Jakobsen, Jyrki Katajainen, and Jukka Teuhola
Published in:Proceedings of the Computing: {T}he 3rd Australasian Theory Symposium, Australian Computer Science Communications 19,2, (1997), 72-78
Abstract:An external heap structure is suggested that tries to make the best use of the available buffer space in main memory. The heap is a multi-way balanced tree, with blocks of records as nodes, satisfying a generalized heap property. The root is buffered, whereas other nodes are kept on secondary storage. A special property of the tree is that the nodes may be partially filled, as with B-trees. The structure is complemented with priority queue operations insert and delete-max. When handling a sequence of these operations, the amortized number of page accesses per operation is shown to be O((1 / P) log(M / P) (N / P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N the largest number of records in the heap (4 P < M < N). This results in optimal external heapsort that performs O((N / P) log(M / P) (N / P)) page accesses in the worst case, when sorting N records.
Related:<html.gif>HTML (Technical report)  <html.gif>HTML (Journal article)  
  author = {Ramzi Fadel and Kim Vagn Jakobsen and Jyrki Katajainen and Jukka
  title = {External heaps combined with effective buffering},
  booktitle = {Proceedings of the Computing: {T}he 3rd Australasian Theory
  series = {Australian Computer Science Communications},
  volume = {19},
  number = {2},
  year = {1997},
  pages = {72--78},
  organization = {Macquarie University},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.