はじめに
界隈で「データ構造をマージする一般的*1なテク」と呼ばれている技法があります．``Introduction to Algorithms'' [1] では Data Structure for Disjoint Sets の章で ``Weighted-Union Heuristic'' として挙げられています． hatena diary の終了に伴い，オリジナルと言えそうな記事が消失してしまったので，二番煎じの二番煎じ*2ながら知っている範囲で書き残しておこうと思います．
データ構造をマージしたい
$n$ 個のデータ構造があり，それを順にマージしたいとします．例えばデータ構造が配列（というか std::vector）であれば，
- 片方の要素を他方へ全て追加
- 移動元のクリア
がマージの例になります（クリアはしなくてもマージできてますが，メモリを圧迫して死にたくないのでセットにしておきます）．これをデータ構造が $1$ 個になるまで行うときの計算量について考えます．
愚直に処理する場合
何も考えずにマージ処理を行っていくとどうなるでしょうか．意地悪なマージ順序を考えてあげると，最長な配列を最短な配列へマージする操作を繰り返すことで，$i$ 回目の操作では $i$ 個の要素が移動することになり，全体の計算量が $\Omega( n^2 )$ となることが分かります．
この計算量は，ちょっとした工夫で減らす事ができます．
Weighted-Union Heuristic
Weighted-Union heuristic はデータ構造のマージ時に常にサイズの大きくない方から小さくない方へマージするようにすることで全体の計算量を $O( n \log n T( n )$ にする技法です．ここで $T( n )$ は 1 つのデータの移動にかかる時間です．
この技法の計算量解析をするにあたっては，視点をちょっと変えてあげることがキモになります．配列に含まれているある要素に着目します．この要素がマージに巻き込まれたとき，マージ時のサイズの取り決めから，それが含まれるデータ構造のサイズは必ず 2 倍以上になります．全体のデータ数が $n$ であることから，ある一つの要素がマージに巻き込まれる回数は $O( \log n )$ 回であることがわかります．よって，すべての要素で考えれば，要素の移動は $O( n \log n )$ 回しか起こりません．全体の計算量はデータの移動回数と移動にかかるコストの積なので，$O( n \log n T( n )$ だと分かりました．
一般性について
この技法は，データの取り出しと挿入がサポートされているデータ構造なら何にでも適用することができ，一般性があります．
おわりに
何番煎じか分かりませんが，Weighted-Union Heuristic の解説でした．遭遇したときに毎回説明を書きたくないので，一つの記事にしておこうという感じのアレです．
参考文献
[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.
