Python高级算法与数据结构：集合的快速查询与合并也可以快速合并成一个集合。比如我们要开发一个社交应用，那么我们就需要用到我们现在提到的功能来判断两个用户是否是好友或者是否属于同一个群组。这些功能看似简单，但有一个难点就是你要处理“够快”。假设a和b的两个元素分别属于集合A和B，判断是否属于同一个集合的直接方法就是遍历集合A中的所有元素，看能不能找到b，如果集合A包含n个元素，那么这种方法的时间复杂度是O(n)，当集合中的元素很多，判断的次数也很多时，这种方法的效率会很低，在本节我们将看看是否可以找到次线性算法。我们先来看复杂度为O(n)的算法逻辑。假设我们有6个元素，编号从0到6。我们可以使用队列来模拟集合。属于同一个集合的元素存储在同一个队列中。然后通过哈希表将每个元素映射到队头，如下图所示：在这种数据结构下，查询两个元素是否属于同一个集合，那么只需要找到队头所在的位置通过哈希表定位各个元素，判断头部是否一致就可以了。我们使用areDisjoint(x,y)来指示两个元素是否属于一个集合。那么areDisjoint在当前数据结构下的时间复杂度为O(1)。如果我们要合并两个元素所在的集合，我们用merge(x,y)来表示，那么在当前结构下，我们只需要找到x和y对应的队头，然后从中遍历x所在的队头指向最后一个元素，然后执行最后一个元素的next指针指向y所在的队头，如下图所示：同时，我们需要再做一个操作，就是修改映射到第二个集合中每个元素的队头，所以在当前结构下，merge(x,y)对应的时间复杂度为O(n)，因为从队头开始遍历到最后是O(n)，同时遍历y所在集合的每个元素，修改它们映射到的队头，时间复杂度也是O(n)。现在的问题是我们是否可以优化合并所需的时间。我们注意到合并有两个耗时的步骤，一个是从队列走到队尾，一个是修改第二个集合中每个元素指向的队头。所以耗时其实是我们用队列来表示集合造成的。为了优化时间，我们将队列替换为多叉树，如下图所示：此时，我们不再使用哈希表将元素映射到队列头部，而是将元素插入同一个集合的进入同一个多叉树中，判断两个元素是否属于同一个集合，我们只需要沿着元素的父节点指针往上走，找到树的根节点。如果找到相同的根节点，则这两个元素属于同一个集合。对于排序对于一棵二叉树，树的高度是O(lg(n))，n是树的节点数，所以判断两个元素是否属于同一个集合所需的时间复杂度是O(lg（n））。当需要合并两组元素对时，我们分别找到这两个元素对的根节点，然后将高度较低的树的根节点作为高度较高的树的子节点。这个处理效率非常重要，我们后面会进一步研究。树合并的情况如下图所示：先看代码实现：#ThisisasamplePythonscript.#Press?Rtoexecuteitorreplaceitwithyourcode.#PressDouble?tosearcheverywhereforclasses,files,toolwindows,actions,andsettings.classElement:def__init__(self,val:int):self.val=valself.parent=self#元素在创建时形成一个单独的集合，所以父节点指向自己defvalue(self):returnsself.valdefparent(self):returnsself.parentdefset_parent(self,parent):assertparentisnotNoneifelem.parent=parentclassDisjontSet:def__init__(self):self.hash_map={}defadd(self,elem:Element):assertelemisnotNoneifelem.value()inself.hash_map:returnFalseself.hash_map[elem.value()]=elemreturnTruedeffind_partition(self,elem:Element):#返回元素所在集合的根节点assertelemisnotNoneorelem.value()inself.hash_mapparent=elem.parent()ifparent!=elem:#递归查找根节点，高度为树是lg(n)，所以时间c这里查找的复杂度是lg(n)parent=self.find_partition(parent)returnparentdefare_disjoint(self,elem1:Element,elem2:Element):#判断两个元素是否属于同一个集合，判断一下就可以了哈哈表中映射的根节点是否相同self.find_partition(elem2)ifroot1isroot2:#两个元素属于同一个setreturnFalseroot2.setParent(root1)self.hash_map[root2.value()]=root1#设置root2对应的父节点#Pressthegreenbuttonintheguttertorunthescript.if__name__=='__main__':#SeePyCharmhelpathttps://www.jetbrains.com/help/pycharm/由于我们将集合的表示方式从队列改为多叉树，相应的搜索合并集合的复杂度为O(lg(n)),现在的问题是我们能否继续提高效率？现在的merge函数的耗时是我们要通过父指针一路爬到根节点。如果父指针可以直接指向根节点，那么就省去了往上爬的时间。将指针直接指向根节点的方法称为路径压缩，如下图所示：从上图可以看出，节点6和8的父节点本来就是9，它所在的集合的根节点是1，所以我们直接指向9指针直接指向根节点1，这样可以省去后面合并或者查询集合的时候爬上去的时间开销。还有一个问题。在上面的代码中，合并了两棵树。我们只是将root2的父指针指向root1。这会导致合并后的树不平衡，即合并后左右子树的高度可能相差很大。这种情况也会对效率产生不利影响，如下图所示：可以看到右下角合并后左右子树的高度差较大，所以节点，6，8找根节点0比2,3长，还有4个多，但是当右上角形成时，叶子节点6,8和2,3,4找根节点的时间差不多，这样有利于提高效率，所以我们还需要记录树的高度，合并的时候要把高度小的树合并成高度大的树，所以代码修改为如下：classElement:def__init__(self,val:int):self.val=valself.parent=self#Element在创建时形成一个单独的Set，所以父节点指向自己self.rank=1#表示高度树defvalue(self):returnsself.valdefparent(self):returnsself.parentdefset_parent(self,parent):assertparentisnotNoneself.parent=parentdefget_rank(self):returnsself.rankdefset_rank(self,rank):assertrank>1self.rank=rank然后我们需要修改find??_partition的方法deffind_partition(self,elem:Element):#返回set的根节点where元素位于assertelemisnotNoneorelem.value()inself.hash_mapparent=elem.parent()ifparentiselem:#已经是根节点returnelemparent=self.find_partition(elem)#获取集合的根节点elem.set_parent(parent)#Pathcompression直接指向根节点returnparent#返回根节点注意find_partion的实现有一个递归过程，如果当前节点不是根节点，则递归查询根节点，然后指向parent指针当前节点直接指向根节点。我们可以看到，这次修改所需要的时间复杂度与原来的一样，都是lg(n)。接下来我们需要修改merge的实现：defmerge(self,elem1:Element,elem2:Element):root1=self.find_partition(elem1)root2=self.find_partition(elem2)ifroot1isroot2:#两个元素属于同一个setreturnFalsenew_rank=root1.get_rank()+root2.get_rank()ifroot1.get_rank()>=root2.get_rank():#根据树的高度确定合并方向root2.set_parent(root1)root1.set_rank(new_rank)else:root1.set_parent(root2)root2.set_rank(new_rank)returnTrue经过这次改进后，m次指向find_partion和merge调用所需的时间为O(m)，也就是说经过改进后，当一个大find_partion和merge被调用的次数，这些平均调用时间减少到O(1)，也就是说路径压缩后，其效果在调用searchset和mergeset操作时可以表现出非常显着的效率提升大批量。相应的数学证明很负责。我们暂时忽略曲调。这里的效率提升我们可能感受不到，但是想想两个人在微信里是不是属于同一个群，一天至少有几千万甚至上亿的调用，所以这里的提升可以大大提升处理效率服务器的。完整代码在这里https://github.com/wycl16514/python_disjoint_set.git
