When an ordinary heap is used for sorting, the siftdown's executed during the second phase of the sort has the characteristic that the element sifted almost always propagates all the way down to the bottom level of the tree. The reason for this is quite obvious.- When the root element is extracted, it is replaced with an element taken from the bottom of the heap. Elements at the bottom of a heap tend to be small.
A similar observation can be made for the external heap. The new root page is almost always shifted unchanged all the way to the bottom of the heap.
This allows two optimizations of the siftdown procedure to be performed.- On each iteration it is checked if the largest element of the parent is less than the smallest element of the larger child. If this is the case, the parent-child merge (figure 6.1) can be replaced with a parent-child swap. Furthermore this swap can be avoided by keeping the parent in a buffer outside the tree and checking if the parent-child merge will result in a swap, before the siblings are merged. Now, the merge of the siblings can be arranged to put the larger elements directly into the parent page, leaving the larger child page empty for the next iteration. Thus in the common case, the two merges executed in each iteration of a siftdown can be reduced to a single merge.
The external cost is not affected by this optimization though. Each iteration must still reference both the parent and its two childrens.