A Hackers guide to (external) heap configurations.

• Basic Heap.- Tree depth is . Performance of heapsort is .
• d-heaps.- 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.