首页 > 代码库 > 普林斯顿公开课 算法1-9:并查集-快速合并
普林斯顿公开课 算法1-9:并查集-快速合并
本节讲的是并查集的另外一种实现方法。这种方法的合并操作开销很小,但是查找操作开销很大。
数据结构
这种算法的数据结构和快速查找方法的数据结构是一样的,也是N个整数组成的数组。
数组中每个元素id[i]的含义是指i的上级是id[i]。
根节点
一个节点的根节点就是id[id[id[...id[i]....]]],一直循环直到数值不再变化为止。由于算法的特性,这种循环永远不会造成死循环。
查找操作
查找操作就是判断两个节点的根节点是否相同。
合并操作
合并节点p和节点q就是将p节点的根节点的父节点设置为q节点的根节点。这样只需要改变一个值,因此开销少了很多。
复杂度
这种方法虽然性能方面提升了很多,但是仍然不够,因为最坏的情况下,查找操作的复杂度将达到N。
对比
快速查找方法中合并的开销太大,但是建立的树结构是平坦的,所以查找操作的开销极小,但是合并操作中建立平坦的树开销非常大。
快速合并方法中树形结构可能会非常高。这种情况下查找操作的开销非常大,复杂度可以达到N。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。