7.2. Array Based Implementation

So, recall that the union find data structure keeps track of a partition of a set S and supports three operations. One is the make union find which creates a trivial partition, where each element belongs to its own, each element is in a single term partition named by itself. Find tells us which partition a given element belongs to and union combines two components or two partitions into a single one.

The union-find data structure is used to manage a collection of disjoint sets (partitions) efficiently. The three main operations are:

1. Make Union-Find: Initializes the structure by assigning each element its own unique partition.
2. Find: Determines which partition a specific element belongs to, helping to identify which elements are connected.
3. Union: Combines two different partitions into a single partition, allowing you to merge sets. Thus, initially, each element is its own set, and over time, we can group them together.

Imagine a classroom where each student (element) sits at their own desk (partition). Initially, each student does their own work without interacting with others. When students work together on a project (union), they form groups. The 'Find' operation is like a teacher asking, "Which group is John in?" to identify the collaborative efforts.

The array-based implementation uses an array called component to tell us which component each element belongs to, it keeps an array of lists to tell us which elements belong to each component. So, it is a kind of reverse mapping, for each component k it tells us which members of the set belong to that. And finally, it keeps track of the size of each component, because we merged components by taking smaller ones and relabeling them with the name of the bigger ones.

In the array-based implementation of union-find:

• A component array is used to assign each element to its respective partition, helping to identify the component for any given element.
• There’s also a reverse mapping that allows tracking of which elements belong to each component.
• The size of each component is maintained to facilitate efficient merging during union operations, ensuring smaller components are combined into larger ones.

Envision a city where each neighborhood is represented in a list. Each neighborhood (component) contains the houses (elements) within it. By keeping a record of which houses belong to which neighborhood, city planners can efficiently merge neighborhoods when a new development is needed.

So, make union-find was an order n operation, find was an order one operation and the amortized complexity of the union operation was log m for a sequence of m operations.

The performance of operations in the array-based implementation is as follows:

• Make Union-Find: O(n) since it initializes the component for each element.
• Find: O(1) (constant time) as it directly accesses the component array to get the partition.
• Union: Amortized O(log m) wherein over a sequence of m union operations, the time taken grows logarithmically due to the combining of smaller sets into larger ones.

This is akin to a group project. Initial team formation might take a long time (O(n)) as everyone gathers. Finding your group partner (Find) is quick since you already know your desk. Yet, combining groups for a major presentation (Union) takes time as you settle in a larger team, typically growing logarithmically as team sizes merge.

So, we will now have a different representation, we will use nodes with pointers. So, each element of the set will now be represented as a node, the node will have two parts, it will have the name which is the element that you are keeping track of and a label part which keeps track of its component, so it is a pointer to the component.

In moving to a pointer-based structure for union-find:

• Each element is now a node consisting of two fields: the name of the element and a pointer pointing to its component. This allows for a more dynamic representation where the structure can flexibly change as elements are combined.
• By using pointers, we can efficiently navigate the data structure despite changes during union operations.

Think of a family tree where each person is a node. Each person (element) knows who their parent (component) is, allowing anyone in the family to navigate up to their ancestors quickly. If a new family member joins (union), links are updated, but each member still knows who their immediate family is, thanks to pointers.

--