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
Oct 4
Lactate threshold
Oct 3
Fairness doctrine
Oct 2
Castle Valley, Utah
Oct 1
2020 Utah gubernatorial election
Sep 30
Tunguska event
Sep 29
Lexicographic order
Sep 28
Cross-site request forgery
Sep 27
Progressive web app
Sep 26
Gerrymandering in the United States
Sep 25
Poisson distribution
Sep 24
Dyatlov Pass incident
Sep 23
Dyatlov Pass incident
Sep 22
Fanum tax
Sep 21
Pollard's p − 1 algorithm
Sep 20
Joe Lo Truglio
Sep 19
Ricky Schroder
Sep 18
Double-entry bookkeeping
Sep 17
Relativistic electromagnetism
Sep 16
97 (number)
Sep 15
Binomial distribution
Sep 14
Analemma
Sep 13
Marvin Heemeyer
Sep 12
Karatsuba algorithm
Sep 11
Ramer–Douglas–Peucker algorithm
Sep 10
Cross-site scripting
Sep 9
Happy Hacking Keyboard
Sep 8
Salted Challenge Response Authentication Mechanism
Sep 7
KHive
Sep 6
Interplanetary Internet
Sep 5
KHive