next up previous contents
Next: The heap property Up: Implementing the external heapsort Previous: Tuning the page size

Heaps with holes


In [5] the idea of a heap with holes is introduced. With this method the size of the heap is kept constant during the sort, by replacing the extracted nodes with holes. The motivation is that during a normal siftdown, two pages are accessed on each level of the tree. If this siftdown can be replaced with a siftup along a line of holes, only one page needs to be accessed on each level of the tree, because one of the two siblings to be merged is already in memory, as the output from the merge on the previous level. Even though the average size of the heap doubles with this arrangement, it only increases the average path length of the tree by one because the heap is a full binary tree.

Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999