mneedham/algorithms2 — pull request #1 by artm (2014-10-20 16:35:47+00:00)
Title: UnionFind optimization

I realize this project is a soltion for a course that ran some years ago, but...

While [answering a question][1] on unix.stackexchange I have wondered if there a ruby implementation of disjoint set existed and came across your [blog post][2] about the implementation of Kruskal algorithm using UnionFind. I had a look at the code and realized that it could be even more efficient. So for the sake of the next person googling for disjoint-set / union-find in ruby I am making this pull request :-)

The key differences are:

1. `UnionFind` maintains a hash of subsets, not just subset leaders. Each subset is an array, shared among its members (so if we have a disjoint set `[1 2] [3]` the corresponding hash could look like `{1 => [1, 2], 2 => [1, 2], 3 => [3]}`, where two `[1, 2]`s are the same array object.

2. When joining two subsets it isn't necessary to iterate over the whole disjoint set as we have the list of elements whose subset is about to change right away. This is the "more efficient" part. It starts making a difference when the structure is sufficiently large.

3. The constructor doesn't prepopulate the structure with singleton subsets, instead it uses Hash constructor with a block, which adds and returns a singleton subset if element isn't in the disjoint set yet. Since the original structure didn't provide the means to query lengthor to iterate over itself, nothing really broke. As a side effect the structure isn't limited to containing natural numbers, it can contain pretty much anything. Constructor doesn't accept size anymore.

I've compared the output of the modified solution against the original and they are identical, looks like I haven't broken anything.

[1]: http://unix.stackexchange.com/a/163152/57441
[2]: http://ruby.dzone.com/articles/algorithm-week-kruskal%E2%80%99s