Improvement 2: Path Compression

  • Trace the Quick Union implementation with path-compression heuristic.
  • Explain the runtime improvements gained by using the heuristic for union-find operations.

After computing the root of $p$, set the ID of each examined node to point to that root.

For example, consider the following tree:

Assume we perform find(J) operation. On our way to find the root, we would pass through $I$, $F$, $B$ until we get to $A$, the root.

We could set all these vertices to directly point to the root, so the tree becomes shallower:

The heuristic described above is known as path compression.