| 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 (Technical report) HTML (Journal article) |
| BibLATEX: | @inproceedings{FJKT1997C,
author = {Ramzi Fadel and Kim Vagn Jakobsen and Jyrki Katajainen and Jukka
Teuhola},
title = {External heaps combined with effective buffering},
booktitle = {Proceedings of the Computing: {T}he 3rd Australasian Theory
Symposium},
series = {Australian Computer Science Communications},
volume = {19},
number = {2},
year = {1997},
pages = {72--78},
organization = {Macquarie University},
}
|