Finding maximum and minimum in union find algorithm

This post is a problem based on union find algorithm. For the algorithm, please see "Weighted Quick Union With Path Compression - Coursera Algorithms"

Problem: Given an element, find the max/min of it's connected components tree.

Following is my, probably brute force, solution to find max/min. For this, we use extra arrays to store the max and min values. We updated the max and min only for root nodes. For all other nodes, just find the root and it's max/min.

	package Union;
	public class CWQuickUnionMaxMin {
	private int[] id;
	private int[] sz;
	private int[] max;
	private int[] min;
	public CWQuickUnionMaxMin(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	sz = new int[N];
	for(int i=0;i<N;i++) {
	sz[i]=1;
	}
	max = new int[N];
	for(int i=0;i<N;i++) {
	max[i]=i;
	}
	min = new int[N];
	for(int i=0;i<N;i++) {
	min[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]+"--------"+sz[i]+"--------"+max[i]+"--------"+min[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	id[i]=id[id[i]];//point each node on path to grandparent to flatten the tree
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	/*
	public int max(int p, int q) {
	return (p>=q? p : q);
	}
	public int min(int p, int q) {
	return (p<=q? p : q);
	}*/
	public int maxInConnComp(int x) {
	int n = id.length;
	int tmp = 0;
	for(int i=0;i<n;i++) {
	if(root(i)==x) {//eles in same component - with same root
	if(i>tmp) {
	tmp = i;
	}
	}
	}
	return tmp;
	}
	public int findMax(int x) {
	return maxInConnComp(root(x));
	}
	public int findMin(int x) {
	return minInConnComp(root(x));
	}
	public int minInConnComp(int x) {
	int n = id.length;
	int tmp = 0;
	for(int i=0;i<n;i++) {
	if(root(i)==x) {//eles in same component - with same root
	if(i<tmp) {
	tmp = i;
	}
	}
	}
	return tmp;
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of small set root to large set root
	//balance trees by always choosing the smaller tree to link up to larger tree
	int proot = root(p),qroot = root(q);
	if(proot==qroot) return;
	if(sz[proot]<sz[qroot]) {
	id[proot] = qroot;
	max[qroot] = maxInConnComp(qroot);
	min[qroot] = minInConnComp(qroot);
	sz[qroot]+=sz[proot];
	}else{
	id[qroot] = proot;
	max[proot] = maxInConnComp(proot);
	min[proot] = minInConnComp(proot);
	sz[proot]+=sz[qroot];
	}
	//print();
	}
	public static void main(String[] args) {
	CWQuickUnionMaxMin cwqu = new CWQuickUnionMaxMin(10);
	cwqu.union(4, 3);
	cwqu.union(3, 8);
	cwqu.union(6, 5);
	cwqu.union(9, 4);
	cwqu.union(2, 1);
	cwqu.connected(0, 7);
	cwqu.connected(8, 9);
	cwqu.union(5, 0);
	cwqu.union(7, 2);
	cwqu.connected(0, 7);
	cwqu.union(6, 1);
	cwqu.union(7,3);
	cwqu.print();
	System.out.println(cwqu.findMax(7));
	System.out.println(cwqu.findMin(7));
	}
	}

view raw CWQuickUnionMaxMin.java hosted with ❤ by GitHub

Weighted Quick Union With Path Compression - Coursera Algorithms

Weighted Quick Union can be improved further by path compression. The idea here is to avoid flatten the tree. After computing the root of a node,  we set the id of each examined node to point to that root.

Running Time:
For M union-find operations on N elements, running time  ≤ c ( N + M lg* N ) array accesses. 

lg*N = number of times we have to take log of N to get 1.

It's almost linear and union find doesn't have any linear algorithm.

Following is the program:

	package Union;
	public class CompressWeightQuickUnion {
	private int[] id;
	private int[] sz;
	public CompressWeightQuickUnion(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	sz = new int[N];
	for(int i=0;i<N;i++) {
	sz[i]=1;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]+"--------"+sz[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	id[i]=id[id[i]];//point each node on path to grandparent to flatten the tree
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of small set root to large set root
	//balance trees by always choosing the smaller tree to link up to larger tree
	int proot = root(p),qroot = root(q);
	if(proot==qroot) return;
	if(sz[proot]<sz[qroot]) {
	id[proot] = qroot;
	sz[qroot]+=sz[proot];
	}else{
	id[qroot] = proot;
	sz[proot]+=sz[qroot];
	}
	//print();
	}
	public static void main(String[] args) {
	CompressWeightQuickUnion cwqu = new CompressWeightQuickUnion(10);
	cwqu.union(4, 3);
	cwqu.union(3, 8);
	cwqu.union(6, 5);
	cwqu.union(9, 4);
	cwqu.union(2, 1);
	cwqu.connected(0, 7);
	cwqu.connected(8, 9);
	cwqu.union(5, 0);
	cwqu.union(7, 2);
	cwqu.connected(0, 7);
	cwqu.union(6, 1);
	cwqu.union(7,3);
	cwqu.print();
	}
	}

view raw CompressWeightQuickUnion.java hosted with ❤ by GitHub

Weighted Quick Union Algorithm - Coursera Algorithms

Quick Find and Quick Union were slow in performing union and finding if two elements are connected respectively. However, Quick Union can be improvised by using weighted trees. The idea here is to avoid tall trees of Quick Union and always balance the trees such that smaller trees always link up to the larger trees.

We use array to initialize elements to indices itself. To weigh trees, we use an extra array to track the size of trees at each element.

Any node x's depth increases by one when it's tree T1 is merged into another T2.
As |T2|>=|T1| , the size of tree containing x at least doubles.
As N*lg N = N, the size of tree containing x can double at most lg N times.
So the depth of any node at x is at most lg N.

Running Time:
initialize - N
union(p,q) - lg N⁺ - including the root calculations
connected(p,q) - lg N - proportional to depth of p and q


Following is the program:

	package Union;
	public class WeightedQuickUnion {
	private int[] id;
	private int[] sz;
	public WeightedQuickUnion(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	sz = new int[N];
	for(int i=0;i<N;i++) {
	sz[i]=1;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]+"--------"+sz[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of small set root to large set root
	//balance trees by always choosing the smaller tree to link up to larger tree
	int proot = root(p),qroot = root(q);
	if(proot==qroot) return;
	if(sz[proot]<sz[qroot]) {
	id[proot] = qroot;
	sz[qroot]+=sz[proot];
	}else{
	id[qroot] = proot;
	sz[proot]+=sz[qroot];
	}
	//print();
	}
	public static void main(String[] args) {
	WeightedQuickUnion wqu = new WeightedQuickUnion(10);
	wqu.union(4, 3);
	wqu.union(3, 8);
	wqu.union(6, 5);
	wqu.union(9, 4);
	wqu.union(2, 1);
	wqu.connected(0, 7);
	wqu.connected(8, 9);
	wqu.union(5, 0);
	wqu.union(7, 2);
	wqu.connected(0, 7);
	wqu.union(6, 1);
	wqu.union(7,3);
	wqu.print();
	}
	}

view raw WeightedQuickUnion.java hosted with ❤ by GitHub

Quick Union Algorithm - Coursera Algorithms

Quick Find was very slow with quadratic operations. Quick Union is a lazy union-find algorithm to unite sets and to see if an element is connected to another. We use array to initialize elements to indices itself. Later, we update the elements to point to it's parent.  This way we create trees out of elements.


Array accesses:
initialize - N
union(p,q) - N⁺ including the cost of root calculations
connected(p,q) -N

The trees can get quite tall, making the connected operation quite slow.

Following is the program:

	package Union;
	public class QuickUnion {
	private int[] id;
	public QuickUnion(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of first set root to second set root
	int proot = root(p),qroot = root(q);
	id[proot] = qroot;
	//print();
	}
	public static void main(String[] args) {
	QuickUnion qu = new QuickUnion(10);
	qu.union(4, 3);
	qu.union(3, 8);
	qu.union(6, 5);
	qu.union(9, 4);
	qu.union(2, 1);
	qu.connected(0, 7);
	qu.connected(8, 9);
	qu.union(5, 0);
	qu.union(7, 2);
	qu.connected(0, 7);
	qu.union(6, 1);
	qu.union(7,3);
	qu.print();
	}
	}

view raw QuickUnion.java hosted with ❤ by GitHub

Quick Find Algorithm - Coursera Algorithms

Quick Find is an eager union-find algorithm.

Purpose: To find if two elements are connected and to perform union operation on two elements.

We will consider the elements as simple int array. We initialize array to index elements itself and then change the ids in the array when an union operation is performed.

Array accesses: 2N+1
initialize - N
union(p,q) - N
connected(p,q) - 1

If N unions are performed on N elements, union takes N² array access. Quadratic operations don't scale.

Following is the program:

	package Union;
	public class QuickFind {
	private int[] id;
	public QuickFind(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]);
	}
	}
	public boolean connected(int p, int q) {
	if(id[p]==id[q])
	return true;
	else
	return false;
	}
	public void union(int p, int q) {
	//get all elements with p's id
	//change ids to q's id
	int n = id.length, pid = id[p], qid = id[q];
	for(int i=0;i<n;i++) {
	if(id[i] == pid) {
	id[i]=qid;
	}
	}
	}
	public static void main(String[] args) {
	QuickFind qf = new QuickFind(10);
	qf.union(4, 3);
	qf.union(3, 8);
	qf.print();
	qf.union(6, 5);
	qf.union(9, 4);
	qf.union(2, 1);
	qf.connected(0, 7);
	qf.connected(8, 9);
	qf.union(5, 0);
	qf.union(7, 2);
	qf.connected(0, 7);
	qf.union(1, 0);
	qf.union(6, 1);
	qf.print();
	}
	}

view raw QuickFind.java hosted with ❤ by GitHub