Every object will be assigned a component identity. The implementation of Quick Find often involves an underlying array or hash map that tracks the component identity of each object. Our implementation uses a hash map (to easily handle the case when objects aren't integers).
Source: CS2040S Lecture Slides
Between the two components, decide on the component d, to represent the combined set. Let the other component's identity be d'. Simply iterate over the component identifier array / map, and for any element with identity d', assign it to d.
Simply use the component identifier array to query for the component identity of the two elements and check if they are equal. This is why this implementation is known as "Quick Find".
| Operation | Time | Notes |
|---|---|---|
| Find | O(1) |
Direct lookup in map |
| Union | O(n) |
Must scan all elements to update identifiers |
Space: O(n) for the component identifier map
-
When to use: Quick Find is suitable when finds vastly outnumber unions. If you have many union operations, consider Weighted Union instead.
-
HashMap vs Array: Our implementation uses
HashMap<T, Integer>to support arbitrary object types. If elements are integers0ton-1, a simple array suffices and is faster. -
Union cost adds up: Performing
nunion operations costsO(n²)total, which becomes prohibitive for large datasets. This is the main limitation of Quick Find.