Skip to content

21.2 Linked-list representation of disjoint sets

21.2-1

Write pseudocode for $\text{MAKE-SET}$, $\text{FIND-SET}$, and $\text{UNION}$ using the linked-list representation and the weighted-union heuristic. Make sure to specify the attributes that you assume for set objects and list objects.

The three algorithms follow the english description and are provided here. There are alternate versions using the weighted union heuristic, suffixed with $\text{WU}$.

1
2
3
4
5
6
7
MAKE-SET(x)
    let o be an object with three fields, next, value, and set
    let L be a linked list object with head = tail = o
    o.next = NIL
    o.set = L
    o.value = x
    return L
1
2
FIND-SET(x)
    return o.set.head.value
1
2
3
4
5
6
7
8
9
UNION(x, y)
    L1 = x.set
    L2 = y.set
    L1.tail.next = L2.head
    z = L2.head
    while z.next != NIL
        z.set = L1
    L1.tail = L2.tail
    return L1

21.2-2

Show the data structure that results and the answers returned by the $\text{FIND-SET}$ operations in the following program. Use the linked-list representation with the weighted-union heuristic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    for i = 1 to 16
        MAKE-SET(x[i])
    for i = 1 to 15 by 2
        UNION(x[i], x[i + 1])
    for i = 1 to 13 by 4
       UNION(x[i], x[i + 2])
    UNION(x[1], x[5])
    UNION(x[11], x[13])
    UNION(x[1], x[10])
    FIND-SET(x[2])
    FIND-SET(x[9])

Assume that if the sets containing $x_i$ and $x_j$ have the same size, then the operation $\text{UNION}(x_i, x_j)$ appends $x_j$'s list onto $x_i$'s list.

Originally we have $16$ sets, each containing $x_i$. In the following, we'll replace $x_i$ by $i$. After the for loop in line 3 we have:

$$\{1,2\}, \{3, 4\}, \{5, 6\}, \{7, 8\}, \{9, 10\}, \{11, 12\}, \{13, 14\}, \{15, 16\}.$$

After the for loop on line 5 we have

$$\{1, 2, 3, 4\}, \{5, 6, 7, 8\}, \{9, 10, 11, 12\}, \{13, 14, 15, 16\}.$$

Line 7 results in:

$$\{1, 2, 3, 4, 5, 6, 7, 8\}, \{9, 10, 11, 12\}, \{13, 14, 15, 16\}.$$

Line 8 results in:

$$\{1, 2, 3, 4, 5, 6, 7, 8\}, \{9, 10, 11, 12, 13, 14, 15, 16\}.$$

Line 9 results in:

$$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\}.$$

$\text{FIND-SET}(x_2)$ and $\text{FIND-SET}(x_9)$ each return pointers to $x_1$.

1
2
3
4
MAKE-SET-WU(x)
    L = MAKE-SET(x)
    L.size = 1
    return L
1
2
3
4
5
6
7
8
UNION-WU(x, y)
    L1 = x.set
    L2 = y.set
    if L1.size  L2.size
        L = UNION(x, y)
    else L = UNION(y, x)
    L.size = L1.size + L2.size
    return L

21.2-3

Adapt the aggregate proof of Theorem 21.1 to obtain amortized time bounds of $O(1)$ for $\text{MAKE-SET}$ and $\text{FIND-SET}$ and $O(\lg n)$ for $\text{UNION}$ using the linked-list representation and the weighted-union heuristic.

(Removed)

21.2-4

Give a tight asymptotic bound on the running time of the sequence of operations in Figure 21.3 assuming the linked-list representation and the weighted-union heuristic.

We call $\text{MAKE-SET}$ $n$ times, which contributes $\Theta(n)$. In each union, the smaller set is of size $1$, so each of these takes $\Theta(1)$ time. Since we union $n - 1$ times, the runtime is $\Theta(n)$.

21.2-5

Professor Gompers suspects that it might be possible to keep just one pointer in each set object, rather than two ($head$ and $tail$), while keeping the number of pointers in each list element at two. Show that the professor's suspicion is well founded by describing how to represent each set by a linked list such that each operation has the same running time as the operations described in this section. Describe also how the operations work. Your scheme should allow for the weighted-union heuristic, with the same effect as described in this section. ($\textit{Hint:}$ Use the tail of a linked list as its set's representative.)

(Removed)

21.2-6

Suggest a simple change to the $\text{UNION}$ procedure for the linked-list representation that removes the need to keep the $tail$ pointer to the last object in each list. Whether or not the weighted-union heuristic is used, your change should not change the asymptotic running time of the $\text{UNION}$ procedure. ($\textit{Hint:}$ Rather than appending one list to another, splice them together.)

(Removed)