Next: What external heaps can
Up: Summary
Previous: Summary

Basic Heap. Tree depth is . Performance of heapsort is
.

dheaps. Increasing the fanout to d reduces the tree depth to
. Heapsort external performance
is . But watch out for the internal cost.
It grows almost linearly with d.

External heaps. With a node size S, the tree depth is
. Heapsort external performance
is .
Notice that the depth of an external heap is exactly the
same as the external depth of a traditional heap where the first
S elements are kept locked in memory.
Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999