5 Disjoint sets: Sub-linear time processing
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 ...
Get Advanced Algorithms and Data Structures now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
