Disjoint-set data structure: Difference between revisions

Revision as of 12:32, 11 July 2023

Revision as of 13:15, 11 July 2023

Line 244:

== Other structures ==

The===Better worst-case time ofper the '''find'''operation===

The worst-case time of the <code>Find</code> operation in trees with '''Union by rank''' or '''Union by weight''' is <math>\Theta(\log n)</math> (i.e., it is <math>O(\log n)</math> and this bound is tight).

In 1985, N. Blum gave an implementation of the operations that does not use path compression, but compresses trees during <math>union</math>. His implementation run in <math>O(\log n / \log\log n)</math> time per operation<ref>{{cite journal |last1=Blum |first1=Norbert |title=On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem |journal=2nd Symp. on Theoretical Aspects of Computer Science |date=1985 |pages=32-38}}</ref>, and thus in comparison with Galler and Fischer's structure it has a better worst-case time per operation, but inferior amortized time. In 1999, Alstrup et al. gave a structure that has optimal worst-case

time <math>O(\log n / \log\log n)</math> together with inverse-Ackermann amortized time.<ref>{{cite journal |last1=Alstrup |first1=Stephen |last2=Ben-Amram |first2=Amir M. |last3=Rauhe |first3=Theis |title=Worst-Case and Amortised Optimality in Union-Find |journal=31st Symp. on Theoretical Aspects of Computer Science |date=1999 |pages=499-506 |doi=10.1145/301250.301383}}</ref>

===Deletion===

The regular implementation as disjoint-set forests does not react favorably to the deletion of elements,

in the sense that the time for <code>Find</code> will not improve as a result of the decrease in the number of elements. However, there exist modern implementations that allow for constant-time deletion and where the time-bound for <code>Find</code> depends on the ''current'' number of elements<ref>{{cite journal |last1=Alstrup |first1=Stephen |last2=Thorup |first2=Mikkel |last3=Gørtz |first3=Inge Li |last4=Rauhe |first4=Theis |last5=Zwick |first5=Uri |title=Union-Find with Constant Time Deletions |journal=ACM Trans. Algorithms |date=2014 |volume=11 |issue=1 |pages=6:1-6:28}}</ref><ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |last2=Yoffe |first2=Simon |title=A simple and efficient Union-Find-Delete algorithm |journal=Theoretical Computer Science |date=2011 |volume=412 |issue=4-5 |pages=487-492}}</ref>

== Applications ==

Line 253 ⟶ 260:

This data structure is used by the [[Boost Graph Library]] to implement its [http://www.boost.org/libs/graph/doc/incremental_components.html Incremental Connected Components] functionality. It is also a key component in implementing [[Kruskal's algorithm]] to find the [[minimum spanning tree]] of a graph.

Note that the regular implementation as disjoint-set forests does not allow the deletion of edges, even without path compression or the rank heuristic. However, there exist modern implementations that allow for constant-time deletion.<ref>{{Cite book |url=https://www.worldcat.org/oclc/262681795 |title=Automata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings |date=2005 |publisher=Springer |others=Luís. Caires, European Association for Theoretical Computer Science |isbn=978-3-540-31691-6 |___location=Berlin |oclc=262681795}}</ref>{{vague citation|date=May 2023}}

The [[Hoshen–Kopelman_algorithm| Hoshen-Kopelman algorithm]] uses a Union-Find in the algorithm.