A well-optimized Union-Find implementation, in Java

Idea

Basically, the class contains two arrays, parents and ranks.

parents stores the parent ID of a given ID.
ranks stores the rank of roots.

It supports two operations, find and union

For find(n1), it will trace back from given ID to its parent, and parent’s parent, until reaching an element without a parent, i.e. a root.
- an optimization here is attaching every elements on this tracing path to the final root, so that the height of the tree is reduced dramatically
For union(n1, n2), first we find the roots of two elements. If two roots are the same, do nothing (but it can be a useful tool to check whether an edge between two nodes makes cycle in a graph). Else, based on the ranks of two roots, we attach one to another to make the tree as balanced as possible.

Analysis

Union

Union operation takes $O(1)$ time.

Find

If we don’t do path shortening, the height of the tree is no more than $O(\log n)$ , $n$ is the number of elements in the tree. Because the tree is balanced and a non-leaf node can have no less than 2 children. The time for a find operation is $O(\log n)$ .

If we do the path shortening, there is a tricky proof says the time complexity for a sequence of $m$ operations is $O((m+n)\sqrt{\log n})$ . There is a even more tricky one to lower this upper bound. I may post the proof later.

Implementation

package unionFind;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class UnionFind {
    private int[] parents;
    private int[] ranks;

    public UnionFind(int size) {
        parents = new int[size];
        Arrays.fill(parents, -1);
        ranks = new int[size];
    }

    public int find(int curId) {
        Queue<Integer> queue = new LinkedList<>();
        while (parents[curId] != -1) {
            queue.offer(curId);
            curId = parents[curId];
        }
        while (!queue.isEmpty()) {
            parents[queue.poll()] = curId;
        }
        return curId;
    }

    public void union(int root1, int root2) {
        root1 = find(root1);
        root2 = find(root2);
        if (root1 == root2) {
            return;
        }
        if (ranks[root1] < ranks[root2]) {
            parents[root1] = root2;
        } else if (ranks[root2] < ranks[root1]) {
            parents[root2] = root1;
        } else {
            ranks[root1]++;
            parents[root2] = root1;
        }
    }
}

AI 2

Algorithm 17

Amazon 1

Authorization 1

Blog 3

Bootstrap 1

C++ 1

CCpp 5

CSS 2

Cloud 3

Code 1

Crawler 1

DNS 1

Database 17

DeepLearning 1

Design 16

Development 1

Docker 1

Express 1

GDB 1

Go 3

Google 4

HTML 3

IOS 1

Java 17

Javascript 4

Jekyll 1

Linux 4

MacOS 2

MachineLearning 16

Markdown 4

Mobile 1

MongoDB 2

Multi-threading 3

NAS 1

Network 11

NeuralNetwork 10

Node 1

OS 8

Public-speaking 1

Python 15

RESTful 1

Rails 9

React 1

Redis 1

Ruby 6

Shell 2

Spring 2

System 16

TCP 1

TDD 1

Thread 2

Vim 1

awk 1

git 1

jQuery 1

media 1

network 1

php 1