union–find data structure
E321042
The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
All labels observed (2)
| Label | Occurrences |
|---|---|
| merge–find set | 1 |
| union–find data structure canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T3043246 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: union–find data structure Context triple: [Robert Tarjan, notableWork, union–find data structure]
-
A.
Huet unification algorithm
The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
-
B.
DSU
DSU is the World Trade Organization’s legal framework that sets out the rules and procedures for resolving trade disputes between member countries.
-
C.
UnionFS
UnionFS is a union file system that allows multiple directories or file systems to be transparently overlaid into a single coherent filesystem view, commonly used for layered container images.
-
D.
LCA
LCA is the three-letter ISO 3166-1 alpha-3 country code assigned to Saint Lucia.
-
E.
LCA
LCA is the common abbreviation for the Lutheran Church in America, a major Lutheran denomination that existed in the United States from 1962 until its merger into the Evangelical Lutheran Church in America in 1988.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: union–find data structure Target entity description: The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
-
A.
Huet unification algorithm
The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
-
B.
DSU
DSU is the World Trade Organization’s legal framework that sets out the rules and procedures for resolving trade disputes between member countries.
-
C.
UnionFS
UnionFS is a union file system that allows multiple directories or file systems to be transparently overlaid into a single coherent filesystem view, commonly used for layered container images.
-
D.
LCA
LCA is the three-letter ISO 3166-1 alpha-3 country code assigned to Saint Lucia.
-
E.
LCA
LCA is the common abbreviation for the Lutheran Church in America, a major Lutheran denomination that existed in the United States from 1962 until its merger into the Evangelical Lutheran Church in America in 1988.
- F. None of above. chosen
Statements (51)
| Predicate | Object |
|---|---|
| instanceOf |
data structure
ⓘ
disjoint-set data structure ⓘ |
| alsoKnownAs |
DSU
ⓘ
disjoint set union ⓘ disjoint-set data structure ⓘ union–find data structure ⓘ
surface form:
merge–find set
|
| applicationDomain |
compilers and type systems
ⓘ
computational geometry ⓘ computer vision ⓘ graph algorithms ⓘ network design ⓘ |
| hasComponent |
parent array
ⓘ
rank array ⓘ size array ⓘ |
| hasKeyIdea |
maintains a partition of a universe into disjoint sets
ⓘ
represents each set by a representative element ⓘ stores sets as rooted trees ⓘ |
| hasOperationDefinition |
find returns the representative of the set containing an element
ⓘ
make-set creates a new set containing a single element ⓘ union merges the sets containing two given elements ⓘ |
| hasOptimization |
path compression
ⓘ
union by rank ⓘ union by size ⓘ |
| mathematicalBasis |
equivalence relations
ⓘ
set partitions ⓘ |
| property |
ensures sets remain disjoint
ⓘ
operations are typically implemented iteratively ⓘ supports efficient merging of equivalence classes ⓘ |
| spaceComplexity | O(n) ⓘ |
| supportsOperation |
connected
ⓘ
find ⓘ make-set ⓘ same-set query ⓘ union ⓘ |
| timeComplexity |
amortized inverse Ackermann time per operation with union by rank and path compression
ⓘ
near-constant time per operation in practice ⓘ |
| typicalImplementation |
array-based parent pointers
ⓘ
tree-based forest representation ⓘ |
| usedInAlgorithm |
Kruskal’s minimum spanning tree algorithm
ⓘ
bridge and articulation point algorithms (as a subroutine in some variants) ⓘ clustering algorithms ⓘ connected components in undirected graphs ⓘ dynamic connectivity problems ⓘ equivalence class computation ⓘ image segmentation ⓘ maze generation algorithms ⓘ network connectivity analysis ⓘ offline lowest common ancestor algorithms ⓘ percolation simulations ⓘ unification in logic and type inference ⓘ |
| worstCaseTimeComplexity | O(α(n)) per operation with union by rank and path compression ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: union–find data structure Description of subject: The union–find data structure is an efficient algorithmic structure that maintains disjoint sets and supports fast union and find operations, widely used in graph algorithms such as Kruskal’s minimum spanning tree.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
merge–find set