Wikipedia Article of the Day
Randomly selected articles from my personal browsing history
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 (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets. While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a disjoint-set forest. This is a specialized type of forest which performs unions and finds in near-constant amortized time. To perform a sequence of m addition, union, or find operations on a disjoint-set forest with n nodes requires total time O(mα(n)), where α(n) is the extremely slow-growing inverse Ackermann function. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times α(n) time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both asymptotically optimal and practically efficient. Disjoint-set data structures play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The importance of minimum spanning trees means that disjoint-set data structures underlie a wide variety of algorithms. In addition, disjoint-set data structures also have applications to symbolic computation, as well as in compilers, especially for register allocation problems.
History
Dec 21
Poisson point process
Dec 20
Generic top-level domain
Dec 19
Beale ciphers
Dec 18
Heavyweight (podcast)
Dec 17
MurmurHash
Dec 16
Attempted assassination of Ronald Reagan
Dec 15
Mnemonic major system
Dec 14
Peter M. Lenkov
Dec 13
Lagrange polynomial
Dec 12
Polynomial interpolation
Dec 11
Newton polynomial
Dec 10
Quantile function
Dec 9
Static site generator
Dec 8
Flag Day (United States)
Dec 7
Seven-segment display character representations
Dec 6
Tori Kelly
Dec 5
Lynn Conway
Dec 4
G7
Dec 3
Nostr
Dec 2
Negative binomial distribution
Dec 1
Toledo War
Nov 30
Laurent series
Nov 29
Interface control document
Nov 28
ANT (network)
Nov 27
Functional analysis
Nov 26
Semiring
Nov 25
Projective set (disambiguation)
Nov 24
Primitive polynomial
Nov 23
Syphilis
Nov 22
Mud dauber