Major improvement to the QuickUnion algorithm.

0-quick-union-path-compression.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).
The QuickUnion algorithm is explained here.

##QuickUnion Path Compression

QuickUnion mostly takes time when finding the roots. While finding the root of a point, we may touch multiple nodes on the way to the root.

If we make all of these nodes (including our initial point) connect to the root once we find it, it will save time later on.

In this way, we make QuickUnion behave a bit more like QuickFind (where all points in a tree point to the root).
This allows us to reduce root-finding and thus speeds up connection checks.

So we still keep the fast union property of QuickUnion, while avoiding the large number id-array changes that plagues QuickFind;
We only optimize the tree when root-finding - so an an "as-needed" basis.

QuickUnionUFComp.java

// forces all nodes along a root-find to point to the root (recursion is self-derived)

public class QuickUnionUFComp{
	private int[] id;

	public QuickUnionUFComp(int N)
	{
		id = new int[N];

		for (int i = 0; i < N; i++){
			id[i] = i;		
		}
	}

	public boolean connected(int p, int q)
	{
		return root(p) == root(q);
	}

	public int root(int p)
	{
		int idp = id[p];
		if(idp != p){
			id[p] = root(idp);
		}
		return id[p];
	}

	public void union(int p, int q)
	{
		id[root(p)] = root(q);
	}

	public void printID()
	{
		StdOut.print("ID array ");
		for (int i = 0; i < id.length; i++)
			StdOut.print("[" + id[i] + "] ");
		StdOut.println("");
	}
}

QuickUnionUFCompGrand.java

// forces all nodes along a root-find to point to their grandparents (as shown in Coursera vid)

public class QuickUnionUFComp{
	private int[] id;

	public QuickUnionUFComp(int N)
	{
		id = new int[N];

		for (int i = 0; i < N; i++){
			id[i] = i;		
		}
	}

	public boolean connected(int p, int q)
	{
		return root(p) == root(q);
	}

	public int root(int p)
	{
		while (p != id[p])
		{
			id[p] = id[id[p]];
			p = id[p];
		}
		return p;
	}

	public void union(int p, int q)
	{
		id[root(p)] = root(q);
	}

	public void printID()
	{
		StdOut.print("ID array ");
		for (int i = 0; i < id.length; i++)
			StdOut.print("[" + id[i] + "] ");
		StdOut.println("");
	}
}