Generic implementation of the Quick-Union algorithm with Path Compression

Question

Working my way through Algorithms, Fourth edition by Robert Sedgewick & Kevin Wayne. I implemented a generic version of the Quick-Union algorithm and added Path Compression (not described in the book) to it.

Mainly I'm looking for feedback on these two aspects and whether I might have overlooked a side effect.

public class WeightedQuickUnionWithPathCompression<T> {
 private final Map<T, T> components = new HashMap<>();
 private final Map<T, Integer> treeSizes = new HashMap<>();
 public WeightedQuickUnionWithPathCompression(T[] components) {
 for (T component : components) {
 this.components.put(component, component);
 this.treeSizes.put(component, 1);
 }
 }
 public void connect(T leftComponent, T rightComponent) {
 Objects.requireNonNull(leftComponent);
 Objects.requireNonNull(rightComponent);
 if (areConnected(leftComponent, rightComponent)) {
 return;
 }
 T leftComponentTree = find(leftComponent);
 T rightComponentTree = find(rightComponent);
 int leftTreeSize = getTreeSize(leftComponentTree);
 int rightTreeSize = getTreeSize(rightComponentTree);
 if (leftTreeSize < rightTreeSize) {
 components.put(leftComponentTree, rightComponentTree);
 treeSizes.put(rightComponentTree, leftTreeSize + rightTreeSize);
 } else {
 components.put(rightComponentTree, leftComponentTree);
 treeSizes.put(leftComponentTree, leftTreeSize + rightTreeSize);
 }
 }
 private T find(T component) {
 while (!component.equals(components.get(component))) {
 components.put(component, components.get(components.get(component))); // Path compression
 component = components.get(component);
 }
 return component;
 }
 private int getTreeSize(T component) {
 return treeSizes.get(component);
 }
 public boolean areConnected(T leftComponent, T rightComponent) {
 Objects.requireNonNull(leftComponent);
 Objects.requireNonNull(rightComponent);
 return find(leftComponent).equals(find(rightComponent));
 }
}

Answer 1

In find() and areConnected(), you should be able to use == rather than .equals() since you are comparing references, not contents.

---

Your find() loop is a bit inefficient:

• You do components.get(component) once during the while condition test, and again during path compression.
• You do components.put(component, ...) during path compression, then immediately lookup components.get(component) to advance the loop.

The remedy is to introduce two temporary variables, which I call parent and grandparent.

I've chosen to write it as a for loop with side-effect assignments, but of course you can choose to use a while loop without side-effect assignments.

private T find(T c) {
 // Lookup with path compression
 for (T parent, grandparent; (parent = components.get(c)) != c; c = grandparent) {
 components.put(c, grandparent = components.get(parent));
 }
 return c;
}

---

connect() calls areConnected(), which performs redundant work. I suggest...

public void connect(T leftComponent, T rightComponent) {
 Objects.requireNonNull(leftComponent);
 Objects.requireNonNull(rightComponent);
 T leftComponentTree = find(leftComponent);
 T rightComponentTree = find(rightComponent);
 if (leftComponentTree == rightComponentTree) {
 return; // Already connected
 }
 ...
}

• Jeroen Vannevel: Invaluable remarks, much appreciated! I've stuck with a while loop inside find(T) because it stays more true to the original algorithm, but the intermediate assignments definitely were an eye-opener.

Answer 2

While I applaud your effort to keep methods short by refactoring, I question the benefit of replacing

treeSizes.get(component)

with a private method call that saves two characters without abstracting or encapsulating anything:

getTreeSize(component)

I'd be curious to see if introducing a private static class to combine the result of find and getTreeSize could simplify connect.

Finally, why bother with the null checks when null values will immediately throw NPE anyway? It would make sense if the check included a message denoting the problem, but all you get here is a line number--no more than without them. Not that this isn't a good habit in general.

• Jeroen Vannevel: You're right about the simplicity of the method. On one hand I like the level of abstraction it brings but at the same time it's not something I expected to change so I'll remove the intermediate method. Could you clarify what you mean with the private class? Good point about the parameter checking as well, I've used the overload instead.