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?
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.
Thanks, I did look at the Wikipedia page, but the Applications section is pretty difficult to read. The applications it lists are themselves quite abstract problems.
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?
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.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Thanks, I did look at the Wikipedia page, but the Applications section is pretty difficult to read. The applications it lists are themselves quite abstract problems.