Union–find: pointer hops per find, four combinations

Union–find: pointer hops per find, four combinations

3 n random unions on n elements, with the two optimisations switched independently. Without either, the mean path length grows with n and reaches 4898 hops at n = 65536. With both, it is 0.92 and has moved by a factor of 1.03 across the whole range. Either optimisation alone gets most of the way; the famous bound is about the pair.

Drawn at 690 × 400, wide on the page. Everything above is what union-find-paths 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 union-find-paths. 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.