I didn’t see it in the docs and am trying to identify what algorithm is used in the implementation of find (and union) in the DisjointSets object in the DataStructures.jl package.
find
The docs say that “path compression” is used for the find operation, which is good enough for (optimal) O(\alpha(n)) complexity, but requires two traversals of a path from node to root. In contrast, the Wikipedia entry notes that path-halving or path-splitting can be used to remove one of the traversals and still retain the optimal complexity (and is fast in practice).
Two questions: (1) am I correct in my understanding that the current implementation does not utilize path-halving or path-splitting? (2) would it be worthwhile to have an implementation of path-compression plus path-halving and path-splitting find operations?
union
It seems the current implementation does union-by-rank (per Wikipedia). By-rank seems to be more space-efficient than by-size.