Union-Find (Disjoint Set Union) nyomon követi az elemek particionálását diszjunkt halmazokra és két majdnem O(1) műveletet támogat: find (melyik halmazban van az x?) és union (két halmaz egyesítése). Kiválóan működik kapcsolódási lekérdezésekhez.
Minden halmaz egy reprezentatív gyökérrel rendelkező fa. és segítségével a műveletek majdnem konstans időben futnak (inverse Ackermann, α(n)).
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # compress
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller under larger
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
Path compression és union by rank nélkül a fák O(n) láncokra degradálódnak. Nem támogatja a halmazok hatékony szétválasztását.
A Union-Find szinte költségmentesen válaszol arra a kérdésre, hogy "összefüggnek-e ezek a dolgok?" hatalmas méretekben.
Ez az erő Kruskal MST-jének és számos gráf- és klaszterezési algoritmusnak a magja.
Két optimizálása egy emlékezetes tanulság arról, hogy a kis szerkezeti trükkök hogyan nyújtanak szinte konstans idejű teljesítményt.