在不相交集算法中按大小联合与按等级联合
union by size vs union by rank in disjoint-set algorithm
问题简而言之：按等级联合是否仅在某些情况下有效？
例如输入为：
(1, 2), (3,4), (3,5)，在我们 运行 一个关于它们的不相交集算法之后：
其中一个正确的输出应该是 (1,2), (3,4,5)。根（2 个集合的代表）分别是 2 和 4。森林应该是这样的：
2 4
\ / \
1 3 5
问题来了，如果我需要按大小降序对输出进行排序（因此较大的大小在前）：
如果我使用 union by size（只是它的后代数量，包括节点本身），size(2) == 2，size(4) == 3，那么正确的集合应该先来一切顺利；
如果我使用union by rank（其高度的上限），rank(2) == 1、rank(4) == 1，左右集合相等，这这不是我想要的。所以 按等级联合 失败了，不好！
这是为什么？这是否意味着 union by rank 有其局限性？如果可以，什么情况下可以使用union by rank？ 大小联合更通用吗？
按等级合并启发式和按大小合并启发式的要点是最小化 Merge 操作的预期 运行 时间。它们不用于任何其他目的。
您的用例显然涉及按大小对集合进行排序，这是一种不寻常但并非闻所未闻的事情。如果您使用按大小并集启发式算法，则无需额外工作即可完成此操作。 （这并不会增加渐近的复杂性，因为即使在按等级合并时，每个集合的大小也可以轻松维护。）因此对于这个用例，听起来按大小合并对您来说更方便。但是他们都在他们设计的上下文中工作。
问题简而言之：按等级联合是否仅在某些情况下有效？
例如输入为：
(1, 2), (3,4), (3,5)，在我们 运行 一个关于它们的不相交集算法之后：
其中一个正确的输出应该是 (1,2), (3,4,5)。根（2 个集合的代表）分别是 2 和 4。森林应该是这样的：
2 4
\ / \
1 3 5
问题来了，如果我需要按大小降序对输出进行排序（因此较大的大小在前）：
如果我使用 union by size（只是它的后代数量，包括节点本身），size(2) == 2，size(4) == 3，那么正确的集合应该先来一切顺利；
如果我使用union by rank（其高度的上限），rank(2) == 1、rank(4) == 1，左右集合相等，这这不是我想要的。所以 按等级联合 失败了，不好！
这是为什么？这是否意味着 union by rank 有其局限性？如果可以，什么情况下可以使用union by rank？ 大小联合更通用吗？
按等级合并启发式和按大小合并启发式的要点是最小化 Merge 操作的预期 运行 时间。它们不用于任何其他目的。
您的用例显然涉及按大小对集合进行排序，这是一种不寻常但并非闻所未闻的事情。如果您使用按大小并集启发式算法，则无需额外工作即可完成此操作。 （这并不会增加渐近的复杂性，因为即使在按等级合并时，每个集合的大小也可以轻松维护。）因此对于这个用例，听起来按大小合并对您来说更方便。但是他们都在他们设计的上下文中工作。