考虑函数,证明:对于n的所有实际值,有,并且有每个节点的秩最多为这一事实,说明如何去修改势函数的参数来证明对于一组m个MAKE-SET,UNION和FIND-SET操作的序列(其中n个是MAKE-SET操作)我们能在一个不相交集合森林上使用按秩合并与路径压缩在最坏情况运行时间内处理完。
MAKE-SET(v){ x.p = x x.rank = 0 } UNION(u,v){ LINK(FIND-SET(u),== FIND-SET(v)) } LINK(x,y){ if x.rank > y.rank y.p = x else x.p = y if x.rank == y.rank y.rank++ } FIND-SET(x){ if x != x.p x.p = FIND-SET(x.p) return x.p }