Union-Find (Disjoint Set Union) sporer en partisjon av elementer inn i disjunkte mengder og støtter to nesten-O(1) operasjoner: find (hvilken mengde er x i?) og union (slå sammen to mengder). Det er utmerket for connectivity spørsmål.
Hver mengde er et tre med en representativ rot. Med og , kjører operasjoner i nesten konstant tid (invers 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
Uten path compression og union by rank degenererer trær til O(n) kjeder. Det støtter ikke effektiv splitting av mengder.
Union-find besvarer "er disse to tingene koblet sammen?" i massiv skala med nesten ingen kostnad.
Det er motoren inne i Kruskal's MST og mange graf- og klusteringsalgoritmer.
Dets to optimaliseringer er en minneverdig leksjon i hvordan små strukturelle triks gir nesten konstant-tids ytelse.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner