Also, I think the 'find' operation could be replaced by an operation that checks if two elements are in the same set. That way you don't have to come up with a "name".
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.
4 Comments
Noughtmare@programming.dev · 1 pts · 1y
Also, I think the 'find' operation could be replaced by an operation that checks if two elements are in the same set. That way you don't have to come up with a "name".
Noughtmare@programming.dev · 1 pts · 1y
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?
solrize@lemmy.world · 2 pts · 1y
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
Noughtmare@programming.dev · 1 pts · 1y
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.