Linked List Representation of Disjoint Sets

The first representation  is the linked list representation.

Each set is stored as a linked list.

The head node is chosen as the representative.

Each node stores

• key
• next pointer
• pointer to representative

The representative stores

• head
• tail
• size (optional)

Example

Figure 19.2(a) shows a simple way to implement a disjoint-set data structure: each set is represented by its own linked list. The object for each set has attributes head,pointing to the ûrst object in the list, and tail, pointing to the last object. Each object in the list contains a set member, a pointer to the next object in the list, and a pointer back to the set object. Within each linked list, the objects may appear in any order. The representative is the set member in the ûrst object in the list.

---

Operations Using Linked Lists

MAKE-SET

To carry out MAKE-SET (x), create a new linked list whose only

object is x .

Time

$$O(1)$$

---

FIND-SET 

Each node contains a pointer directly to the representative.

For FIND-SET(x), just follow the pointer from x back to its set object and then return the member in the object that head points to. 

For example, in Figure 19.2(a), the call FIND-SET (g) returns f .

Time

$$O(1)$$

---

UNION

Suppose

List 1

1 →2 →3

and

List 2

4 →5

Append second list to first

1→2→3→4→5

Update representative pointer of

4

5

to point to

1

---

Cost of UNION

Appending lists is easy.

The expensive step is

Updating representative pointers.

If the second list contains

k

elements,

cost

$$O(k)$$

As Figure 19.2(b) shows, the operation UNION(x; y) appends y ’s list onto the end of x ’s list. The representative of x ’s list becomes the representative of the resulting set.To quickly find where to append y ’s list, use the tail pointer for x ’s list. Because all members of y ’s list join x ’s list, the UNION operation destroys the set object for y’s list. The UNION operation is where this implementation pays the price for FIND-SET taking constant time: UNION must also update the pointer to the set object for each object originally on y ’s list, which takes time linear in the length of y ’s list. In Figure 19.2, for example, the operation UNION(g,e) causes pointers to be updated in the objects for b, c , e, and h.

---

Weighted Union Heuristic

We can use  the weighted-union heuristic to improve performance.

Idea

Always append

smaller list

to

larger list.

always move the shorter list.which requires min updates.

---

Example

Large

1→2→3→4→5→6→7→8

Small

9→10

Append

9→10

to large

1→2→3→4→5→6→7→8→9→10

Only

9

10

need representative updates.

Suppose instead that each list also includes the length of the list (which can be maintained straightforwardly with constant overhead) and that the UNION procedure always appends the shorter list onto the longer, breaking ties arbitrarily.With this simple weighted-union heuristic, a single UNION operation can still take minimum time Ω(n) if both sets have n members

---

Complexity Analysis

Suppose an element's representative pointer changes.

Each time it changes, the size of the containing set at least doubles.

Example

1
↓

2
↓

4
↓

8
↓

16

Maximum doublings

$$\log_2 n$$

Therefore,

each element changes representative at most

$$\log n$$

times.

Hence

Total time for

m operations

$$O(m+n\log n)$$

This is much better than the naïve implementation.

Theorem 

Using the weighted-union heuristic with linked lists, a sequence of m MAKE-SET, UNION, and FIND-SET operations on n elements takes

$$O(m+n\log n)$$

where

• n = total number of MAKE-SET operations (number of elements created)
• m = total number of operations (MAKE-SET + UNION + FIND-SET)