MIT 6.1220 — Lecture 3

DSU and Amortized Analysis

Problem. (Disjoint Set) Consider a collection of pairwise disjoint sets $\text{DS} := \{ S_1, S_2, \dots, S_r\}$ , where each set $S_i$ contains a single representative $\textsc{Rep}[S_i] \in S_i$ . Suppose $\text{DS}$ supports the following operations:

$\textsc{Make-Set}(x)$ : Adds $\{x\}$ to $\text{DS}$ , with $\textsc{Rep}[\{x\}] = x$ .
$\textsc{Find-Set}(x)$ : Returns $\textsc{Rep}[S(x)]$ , where $S(x)$ is the set containing $x$ .
$\textsc{Union}(x, y)$ : Replaces $S(x)$ and $S(y)$ with $S(x) \sqcup S(y)$ and sets $\textsc{Rep}[S(x) \sqcup S(y)]$ to $\textsc{Rep}[S(x)]$ or $\textsc{Rep}[S(y)]$ .

This data structure is called the Union Find data structure.

The idea is to say each set is a doubly-linked list. For example,

\text{DS} = \{ \{3, 9, 4\}, \ \{2, 7, 1, 8\} \} ~ \implies ~ \{ 3 \leftrightarrow 9 \leftrightarrow 4 \} \text{ and } \{ 2 \leftrightarrow 7 \leftrightarrow 1 \leftrightarrow 8 \}.

So each element in each $S_i$ has a prev and next pointer. And we'll say $\textsc{Rep}[S_i]$ is the head of $S_i$ .

Solution. (Disjoint Set #1) If every $S_i$ is a doubly-linked list, then:

$\textsc{Make-Set}(x)$ : Trivial.
$\textsc{Find-Set}(x)$ : Repeatedly follow prev pointers until you reach the head.
$\textsc{Union}(x, y)$ : Use prev and next to find the head and tail of $S(x)$ and $S(y)$ , respectively. Link them.

The time complexity achieved here is:

\textsc{Make-Set}: \Theta(1) ~~~~~~ \textsc{Find-Set}(x): \Theta(|S(x)|) ~~~~~~ \textsc{Union}(x, y): \Theta(|S(x)| + |S(y)|).

But this is a little silly. It shouldn't take $\Theta(|S(x)|)$ just to find the head; $S(x)$ can just store the head in metadata.

Solution. (Disjoint Set #2) Every element now furthermore points to a metadata object pointing to the head.

$\textsc{Make-Set}(x)$ : Trivial, still $\Theta(1)$ .
$\textsc{Find-Set}(x)$ : Now also trivially $\Theta(1)$ , since you can just read the metadata.
$\textsc{Union}(x, y)$ : Now $\Theta(|S(y)|)$ , because you need all elements in $S(y)$ to point to new metadata.

But we can do even better by considering an amortized analysis.

Definition (Amortized Cost). A data structure $\mathbf{D}$ has an amortized cost of $T$ if any sequence of $k$ operations starting from the initial state of $\mathbf{D}$ has a total cost at most $k \cdot T$ .

Solution. (Disjoint Set #3) Let's be smarter about handling $\textsc{Union}(x, y)$ : always merge so that $|S(y)| \leq |S(x)|$ . We claim this yields an amortized cost of $\Theta(\log n)$ , where $n := \sum_{i = 1}^r |S_i|$ .

Proof: Any individual element has its pointer updated at most $O(\log n)$ times, so Union steps take at most $O(n \log n)$ time. Every other step takes $\Theta(1)$ time. And $k \geq n$ . $\blacksquare$

More generally, there are three strategies for computing amortized cost.

Aggregate Method: What we did just now. Just compute the cost as a function of $k$ , then divide by $k$ .
Accounting Method: We'll discuss this in recitation!
Potential Method: Define a potential function $\Phi: \text{DS} \to \mathbb{R}^{\geq 0}$ , with $\Phi_i := \Phi(\text{DS}_i)$ , forced to satisfy $\Phi_0 = 0$ .

Suppose the real costs of $k$ operations are $c_1, c_2, \dots, c_k$ . Define fake cost by $\hat{c_i} := c_i + \Phi_i - \Phi_{i - 1}$ . Note that:
$\sum_{i = 1}^k \hat{c_i} = \sum_{i = 1}^k \left [ c_i + (\Phi_i - \Phi_{i - 1}) \right ] = (\Phi_k - \Phi_0) + \sum_{i = 1}^k c_i \geq \sum_{i = 1}^k c_i.$
Thus, we can bound $\sum_{i = 1}^k c_i$ by bounding $\sum_{i = 1}^k \hat{c_i}$ instead. And maybe the latter is easier.

Solution. (Disjoint Set #4) Every set is now a rooted tree.

$\textsc{Make-Set}(x)$ : Create a singleton tree in $\Theta(1)$ time.
$\textsc{Find-Set}(x)$ : Follow parent pointers from $x$ until you reach the root. This is $\Theta(|S(x)|)$ in the worst case.
$\textsc{Union}(x, y)$ : Find the roots, then point one root to the other. This is $\Theta(|S(x)| + |S(y)|)$ in the worst case.

Obviously this is pretty bad. But let's be smarter.

Solution. (Disjoint Set #5) In $\textsc{Union}$ , point roots from the shorter tree to the taller tree (by tree height).

$\textsc{Make-Set}(x)$ : The same thing, still $\Theta(1)$ .
$\textsc{Find-Set}(x)$ : Now reduced to $O(\log n)$ because any tree can have height at most $\log n$ . (Trees are balanced.)
$\textsc{Union}(x, y)$ : Also $O(\log n)$ .

Great! We have a second solution that yields $O(\log n)$ amortized cost. Let's get one more third solution:

Solution. (Disjoint Set #6) Any time we perform “traversal to the root”, compress the tree!

(u_1 \to u_2 \to \dots \to u_m \to R) ~ \implies ~ (u_1 \to R, ~~ u_2 \to R, ~~ \dots, ~~ u_m \to R)

We claim this also yields an amortized cost of $O(\log n)$ .

Proof: Define the potential by $\Phi := \sum_{x \in V} \log (L(x))$ , where $L(x)$ denotes the size of the subtree rooted at $x$ .

$\textsc{Make-Set}(x)$ : Yields $\Delta \Phi_i = 0$ .
$\textsc{Find-Set}(x)$ : Suppose this step reroots $u_1 \to u_2 \to \dots \to u_m \to R$ . Then:
$\Delta \Phi_i = \sum_{j = 2}^{m} \left [ \log (L(u_j) - L(u_{j - 1})) - \log (L(u_j)) \right ] = \sum_{j = 2}^m \log \left ( 1 - \dfrac{L(u_{j - 1})}{L(u_j)}\right).$
We can now bound $\hat{c_i}$ , with a computational trick that makes it clean:
$\begin{align*}\hat{c_i} = m + \sum_{j = 2}^m \log \left(1 - \dfrac{L(u_{j - 1})}{L(u_j)} \right) = 1 + \sum_{j = 2}^m \left [ 1 + \log \left(1 - \dfrac{L(u_{j - 1})}{L(u_j)}\right) \right ].\end{align*}$
Importantly, we have the following (check this!):
$1 + \log \left(1 - \dfrac{L(u_{j - 1})}{L(u_j)}\right) \begin{cases} \in [0, 1] & \text{for at most } O(\log n) \text{ values of } j. \\ <0 & \text{for all other values of } j. \end{cases}$
This justifies why $\textsc{Find-Set}$ operations have amortized cost $O(\log n)$ .
$\textsc{Union}(x, y)$ : This step is the combination of $\textsc{Find-Set}(x)$ and $\textsc{Find-Set}(y)$ , plus a merge.

The two $\textsc{Find-Set}$ operations have $O(\log n)$ amortized cost. The merge has a fake cost of:
$\log (L(x) + L(y)) - \log (L(x)) = \log \left ( 1 + \dfrac{L(y)}{L(x)} \right) = O( \log n).$
So the $\textsc{Union}$ operation also has amortized cost $O(\log n)$ .

And so this solution also has $O(\log n)$ amortized cost overall. $\blacksquare$

It turns out that if you combine the approaches of Disjoint Set #5 and Disjoint Set #6, you get a solution with $O(\alpha(n))$ amortized cost, where $\alpha$ is the Inverse-Ackermann Function. For most reasonable $n$ , we have $\alpha(n) \leq 4$ .