Tento datový typ byl poprvé popsán Bernard A. Galler a Michael J. Fischer v roce 1964. Podporuje 3 operace nad danou množinou S={x1, … , xn} n prvků:
Operace
| Operace | Popis | Složitost |
|---|---|---|
init |
Vytvoří rozklad S do n jedno prvkových disjunktních podmnožin {x1}, … ,{xn} | O(1) |
find |
vrátí identifikaci podmnožiny, do které prvek x momentálně patří. | |
union |
Sloučí dvě disjunktní podmnožiny S1 a S2 do jedné. | O(log n) |
Tato datová struktura je vhodná a přirozená pro algoritmické (snadno paralelizovatelné) řešení dalších problémů, např.
- konstrukce souvislých komponent grafu,
- hraje klíčovou roli v Kruskalově algoritmu pro hledání minimální kostry grafu,
- detekce cyklu v grafu.