One thing I'm missing is which problems this technique can solve. I believe one important use case is in type inference. Are there many other problems that can be solved by union-find?
this post was submitted on 03 Nov 2024
0 points (NaN% liked)
Haskell
505 readers
1 users here now
founded 2 years ago
MODERATORS
The Wikipedia article discusses some applications. One amazing thing I remembered about the algorithm is its running time, which is infinitesimally slower than linear, by which I mean that the growth factor above linear is the inverse Ackermann function! I've never studied the analysis but I found the result to be mind boggling.