This chapter covers
- Solving the problem of keeping a set partitioned into disjoint sets and merging partitions dynamically
- Describing an API for a data structure for disjoint sets
- Providing a simple linear-time solution for all methods
- Improving the running time by using the right underlying data structure
- Adding easy-to-implement heuristics to get quasi-constant running time
- Recognizing use cases where the best solution is needed for performance
In this chapter we are going to introduce a problem that seems quite trivial—so trivial that many developers wouldn’t even consider it worth a performance analysis, so they’d just implement the obvious solution to it. Nevertheless, if the expression “wolf in sheep’s clothing” was applied to data structures, this would be the best heading for this chapter.