Union-Find Data Structure

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Identify the operations of the Union-Find data structure.
• Trace the quick find implementation strategy for union-find.
• Trace the quick union implementation strategy for union-find.
• Differentiate the advantages/disadvantages of quick find vs. quick union.
• Trace the "quick union" implementation with union-by-size and path compression heuristics.
• Explain the runtime improvements gained by using the heuristics for union-find operations.
• Define the iterated logarithm (log-star) function.
• Identify the amortized runtime of union-find operations.
• Explain how to implement Kruskal's algorithm efficiently using a union-find structure to detect cycles. Identify the resulting time complexity.

This chapter does not have a starter/solution code.