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 
if
the siftdown can be implemented as efficiently as for the
traditional heap. I.e. with external running time of 
.