1.5.14

1.5.14 #

解答 #

WeightedQuickUnionByHeight 的官方实现：WeightedQuickUnionByHeightUF.java。

证明：一次 Union 操作只可能发生如下两种情况。

两棵树的高度相同，这样合并后的新树的高度等于较大那棵树的高度 + 1。
两棵树的高度不同，这样合并后的新树高度等于较大那棵树的高度。

现在证明通过加权 quick-union 算法构造的高度为 h 的树至少包含 2h 个结点。

基础情况，高度 h = 0, 结点数 k = 1。

为了使高度增加，必须用一棵高度相同的树合并，而 h = 0 时结点数一定是 1，则：

h = 1, k = 2

由于两棵大小不同的树合并，最大高度不会增加，只会增加结点数。

因此，每次都使用相同高度的最小树进行合并，有：

h = 2, k = 4
h = 3, k = 8
h = 4, k = 16
......

递推即可得到结论，k ≥ 2^h

因此 h <= lgk

代码 #

public class WeightedQuickUnionByHeightUf : QuickUnionUf
{
    private readonly int[] _height;

    /// <summary>
    /// 新建一个以高度作为判断依据的加权 quick-union 并查集。
    /// </summary>
    /// <param name="n">新建并查集的大小。</param>
    public WeightedQuickUnionByHeightUf(int n) : base(n)
    {
        _height = new int[n];
        for (var i = 0; i < n; i++)
        {
            _height[i] = 0;
        }
    }

    /// <summary>
    /// 将两个结点所属的连通分量合并。
    /// </summary>
    /// <param name="p">需要合并的结点。</param>
    /// <param name="q">需要合并的另一个结点。</param>
    public override void Union(int p, int q)
    {
        var rootP = Find(p);
        var rootQ = Find(q);

        if (rootP == rootQ)
        {
            return;
        }

        if (_height[rootP] < _height[rootQ])
        {
            Parent[rootP] = rootQ;
        }
        else if (_height[rootP] > _height[rootQ])
        {
            Parent[rootQ] = rootP;
        }
        else
        {
            Parent[rootQ] = rootP;
            _height[rootP]++;
        }
        TotalCount--;
    }
}

另请参阅 #

UnionFind 库