素集合データ構造
素集合データ構造を生成する単純な手法としては、集合毎に連結リストを生成する方法がある。リストの先頭の要素がその集合の代表となる。
MakeSetは1要素のリストを生成する。Unionは2つのリストを連結する操作で、定数時間の操作である。この実装の欠点は、FindがΩ(n)または線形時間を必要とする点である。
これを防ぐには、連結リストの各ノードにそのリストの先頭へのポインタを格納しておけばよい。つまり、Findの引数がノードへのポインタであれば、即座にそのノードが属するリストの先頭(代表)がわかる。しかし、このように実装すると今度はUnion操作で各ノードの先頭へのポインタを更新しなければならなくなり、Ω(n) の時間がかかるようになる。
各リストの長さがわかっているなら、短い方を長い方に連結することでUnionの性能を改善できる。これ (weighted-union heuristic) を採用すると、n個の要素について、m回のMakeSet、Union、Find操作を行ったときにかかる時間は O(m + nlog n) となる。漸近的により高速な操作には別のデータ構造が必要である。