Heaps and heapsort on secondary storage |
| |
Authors: | R Fadel K V Jakobsen J Katajainen J Teuhola |
| |
Affiliation: | a Department of Computing, University of Copenhagen, Universitetsparken 1, DK-2100, Copenhagen East, Denmark b Department of Computer Science, University of Turku, Lemminkäisenkatu 14 A, FIN-20520, Turku, Finland |
| |
Abstract: | 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> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑i = 1S log2 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. |
| |
Keywords: | Secondary storage Priority queues Heaps Sorting Heapsort |
本文献已被 ScienceDirect 等数据库收录! |
|