next up previous contents
Next: The external siftdown procedure Up: The External Heapsort Previous: The External Heapsort

The data structure of external heaps

The data structure of an external heap differs from the heaps seen so far, in that the nodes of the heap are not single elements, but blocks of elements. As a natural consequence the heap property must then be reformulated to specify an ordering of blocks rather than of elements.

The external heap property. In every node, all elements must be larger than every element in any descendant node.

With this formulation the S largest elements in the heap can be found in the top node. Since our purpose is to specialize the heap for sorting, this is important because it allows us to remove all S top elements in one operation. As a result the siftdown procedure is only invoked once for every S elements for a total of M invocations, and the external cost of the heapsort drops to tex2html_wrap_inline1353 if the siftdown can be implemented as efficiently as for the traditional heap. I.e. with external running time of tex2html_wrap_inline1377 .

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