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}$.
MAKE-SET(x)
// Assume x is a pointer to a node contains .key .set .next
Create a node S contains .head .tail .size
x.set = S
x.next = NIL
S.head = x
S.tail = x
S.size = 1
return S
UNION(x, y)
S1 = x.set
S2 = y.set
if S1.size >= S2.size
S1.tail.next = S2.head
z = S2.head
while z != NIL // z.next is incorrect, so S2.tail node should not be updated
z.set = S1
z = z.next
S1.tail = S2.tail
S1.size = S1.size + S2.size // Update the size of set
return S1
else
same procedure as above
change x to y
change S1 to S2
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.
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$.
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.
During the proof of theorem 21.1, we concluded that the time for the $n$ $\text{UNION}$ operations to run was at most $O(n \lg n)$. This means that each of them took an amortized time of at most $O(\lg n)$. Also, since there is only a constant actual amount of work in performing $\text{MAKE-SET}$ and $\text{FIND-SET}$ operations, and none of that ease is used to offset costs of $\text{UNION}$ operations, they both have $O(1)$ runtime.
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.)
For each member of the set, we will make its first field which used to point back to the set object point instead to the last element of the linked list. Then, given any set, we can find its last element by going ot the head and following the pointer that that object maintains to the last element of the linked list. This only requires following exactly two pointers, so it takes a constant amount of time. Some care must be taken when unioning these modified sets. Since the set representative is the last element in the set, when we combine two linked lists, we place the smaller of the two sets before the larger, since we need to update their set representative pointers, unlike the original situation, where we update the representative of the objects that are placed on to the end of the linked list.
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.)
Instead of appending the second list to the end of the first, we can imagine splicing it into the first list, in between the head and the elements. Store a pointer to the first element in $S_1$. Then for each element $x$ in $S_2$, set $x.head = S_1.head$. When the last element of $S_2$ is reached, set its next pointer to the first element of $S_1$. If we always let $S_2$ play the role of the smaller set, this works well with the weighted-union heuristic and don't affect the asymptotic running time of $\text{UNION}$.