Building a heap two ways, random input

Building a heap two ways, random input

Comparisons against n on logarithmic axes. Bottom-up construction fits n at 1.86 comparisons per element. Repeated insertion is quoted as n log n, and on this input the flattest class for it is n at a spread of 1.09; at n = 65,536 it costs 1.21 times the bottom-up count, against a log₂ n of 16. The famous logarithmic factor is a worst case and this is not the worst case.

Drawn at 690 × 410, wide on the page. Everything above is what heap-build returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

1 essay calls heap-build. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.