Live briefing
Everything about Disjoint-set data structure
Data structure for storing non-overlapping sets
In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets, and finding a representative member of a set. The last operation makes it possible to determine efficiently whether any two elements belong to the same set or to different sets. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Disjoint-set data structureA 5-minute orientation
- Pick up a classic book: Introduction to AlgorithmsThe most-reprinted book on the subject
- Read the landmark paper: Data structures and algorithms for disjoint set union problemsCited 134 times
- Go sideways: Tarjan's off-line lowest common ancestors algorithmA closely related topic
- Go sideways: Link/cut treeA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
đź“š Books worth reading
Introduction to AlgorithmsThomas H. Cormen, Charles E. Leiserson · 1990
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Fundamentals of data structures in CEllis Horowitz · 1993
Computer algorithmsEllis Horowitz · 1997
Fundamentals of computer algorithmsEllis Horowitz · 1978
Data Structures and Algorithms in JavaMichael T. Goodrich, Roberto Tamassia · 2014
Design Analysis and AlgorithmsHari Mohan Pandey · 2008
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Tarjan's off-line lowest common ancestors algorithm In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a…
- Link/cut tree A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations: Add a tree consisting of a single…
- Splay tree A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary…
- Fibonacci heap In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better…
- Brodal queue In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: O(1) for insertion, find-minimum, meld (merge…
- Interval union-split-find In computer science, an interval union-split-find data structure is a data structure that stores a partition of the integer interval [1,n] into intervals…
- Pairing heap A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael…
- Binomial heap In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap)…