1.5.14

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

WeightedQuickUnionByHeight 的官方实现:WeightedQuickUnionByHeightUF.java

证明:
一次 Union 操作只可能发生如下两种情况。
1.两棵树的高度相同,这样合并后的新树的高度等于较大那棵树的高度 + 1。
2.两棵树的高度不同,这样合并后的新树高度等于较大那棵树的高度。

现在证明通过加权 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

代码

namespace UnionFind
{
    public class WeightedQuickUnionByHeightUF : QuickUnionUF
    {
        private int[] height;

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

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

            if (rootP == rootQ)
            {
                return;
            }

            if (this.height[rootP] < this.height[rootQ])
            {
                this.parent[rootP] = rootQ;
            }
            else if (this.height[rootP] > this.height[rootQ])
            {
                this.parent[rootQ] = rootP;
            }
            else
            {
                this.parent[rootQ] = rootP;
                this.height[rootP]++;
            }
            this.count--;
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题