一分钟说清楚并查集
分离集合(disjoint set)是一种经典的数据结构,它有三类操作:
Make-set(a):生成包含一个元素a的集合S;
Union(X, Y):合并两个集合X和Y;
Find-set(a):查找元素a所在集合S,即通过元素找集合句柄;
它非常适合用来解决集合合并与查找的问题,也常称为并查集。
一、并查集的链表实现
如上图,并查集可以用链表来实现。
链表实现的并查集,Find-set(a)的时间复杂度是多少?
集合里的每个元素,都指向“集合的句柄”,这样可以使得“查找元素a所在集合S”,即Find-set(a)操作在O(1)的时间内完成。
链表实现的并查集,Union(X, Y)的时间复杂度是多少?
假设有集合:
S1={7,3,1,4}
S2={1,6}
合并S1和S2两个集合,需要做两件事情:
(1) 第一个集合的尾元素,链向第二个集合的头元素(蓝线1);
(2) 第二个集合的所有元素,指向第一个集合的句柄(蓝线2,3);
合并完的效果是:
变成了一个更大的集合S1。
集合合并时,将短的链表,往长的链表上接,这样变动的元素更少,这个优化叫做“加权合并”。
画外音:实现的过程中,集合句柄要存储元素个数,头元素,尾元素等属性,以方便上述操作进行。
假设每个集合的平均元素个数是n,Union(X, Y)操作的时间复杂度是O(n)。
能不能Find-set(a)与Union(X, Y)都在O(1)的时间内完成呢?
可以,这就引发了并查集的第二种实现方法。
二、并查集的有根树实现
什么是有根树,和普通的树有什么不同?
常用的set,就是用普通的二叉树实现的,其元素的数据结构是:
element{
int data;
element* left;
element* right;
}
通过左指针与右指针,父亲节点指向儿子节点。
而有根树,其元素的数据结构是:
element{
int data;
element* parent;
}
通过儿子节点,指向父亲节点。
假设有集合:
S1={7,3,1,4}
S2={1,6}
通过如果通过有根树表示,可能是这样的:
所有的元素,都通过parent指针指向集合句柄,所有元素的Find-set(a)的时间复杂度也是O(1)。
画外音:假设集合的首个元素,代表集合句柄。
有根树实现的并查集,Union(X, Y)的过程如何?时间复杂度是多少?
通过有根树实现并查集,集合合并时,直接将一个集合句柄,指向另一个集合即可。
如上图所示,S2的句柄,指向S1的句柄,集合合并完成:S2消亡,S1变为了更大的集合。
容易知道,集合合并的时间复杂度为O(1)。
会发现,集合合并之后,有根树的高度变高了,与“加权合并”的优化思路类似,总是把节点数少的有根树,指向节点数多的有根树(更确切的说,是高度矮的树,指向高度高的树),这个优化叫做“按秩合并”。
新的问题来了,集合合并之后,不是所有元素的Find-set(a)操作都是O(1)了,怎么办?
如图S1与S2合并后的新S1,首次“通过元素6来找新S1的句柄”,不能在O(1)的时间内完成了,需要两次操作。
但为了让未来“通过元素6来找新S1的句柄”的操作能够在O(1)的时间内完成,在首次进行Find-set(“6”)时,就要将元素6“寻根”路径上的所有元素,都指向集合句柄,如下图。
某个元素如果不直接指向集合句柄,首次Find-set(a)操作的过程中,会将该路径上的所有元素都直接指向句柄,这个优化叫做“路径压缩”。
画外音:路径上的元素第二次执行Find-set(a)时,时间复杂度就是O(1)了。
实施“路径压缩”优化之后,Find-set的平均时间复杂度仍是O(1)。
结论
通过链表实现并查集:
● Find-set的时间复杂度,是 O(1) 常数时间● Union的时间复杂度,是集合平均元素个数,即 线性时间
画外音:别忘了“加权合并”优化。
通过有根树实现并查集:
● Union的时间复杂度,是 O(1) 常数时间● Find-set的时间复杂度,通过“按秩合并”与“路径压缩”优化后,平均时间复杂度 也是O(1)
使用并查集,非常适合解决“微信群覆盖”问题。
思路比结论重要,有收获就是好的。
原文发布时间为:2018-11-20
本文作者:58沈剑
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
【.NET Core项目实战-统一认证平台】第六章 网关篇-自定义客户端授权
原文: 【.NET Core项目实战-统一认证平台】第六章 网关篇-自定义客户端授权 【.NET Core项目实战-统一认证平台】开篇及目录索引 上篇文章我们介绍了网关使用Redis进行缓存,并介绍了如何进行缓存实现,缓存信息清理接口的使用。本篇我们将介绍如何实现网关自定义客户端授权,实现可以为不同的接入客户端设置不同的访问权限。 .netcore项目实战交流群(637326624),有兴趣的朋友可以在群里交流讨论。 一、功能描述 网关重点功能之一鉴权,需要实现对不同的客户端进行授权访问,禁止访问未经授权的路由地址,且需要对无权访问的请求,返回通用的格式。 比如网关有1-10个可用路由,客户端A只能访问1-5,客户端B只能访问6-10,这时我们就无法通过Ocelot配置授权来进行自定义认证,这块就需要我们增加自定义的认证管道来实现功能,尽量不影响网关已有的功能。 下面我们就该功能如何实现展开讲解,希望大家先理解下功能需求,然后在延伸到具体实现。 二、数据库设计 我在第三章 网关篇-数据库存储配置(1)中讲解了我们网关配置信息设计,本篇将在那个基础上增加客户端认证需要用到的表的相关设计,...
- 下一篇
负载均衡获得真实源IP的6种方法
获得真实IP的6种方法 当数据包从负载均衡器往后端转发时候,真实源IP可在L3、L4、L7实现,并且分别有2种方法可以获得真实IP,因此共有6种方法: 保持L3层源IP不变,根据连接次数可以分为 ● 一次连接模式,如lvs ● 二次连接模式,如haproxy的透明模式 在L4层数据里,添加源IP信息,有2种模式 ● 在4层的option字段里增加源IP信息,比如tcp option、udp option ● 在4层末尾和7层开头之间,增加proxy protocol信息 在L7层数据里,增加源IP信息,有2种模式 ● 协议自带,例如HTTP的X-FORWARD-FOR ●业务程序自行实现 一次连接与二次连接 一次连接:负载均衡器对数据包仅做转发,而不对后端重新发起三次握手 二次连接:和一次连接相对应,在tcp转发时候,对后端重新进行了三次握手。上面所讲的L4和L7方法的负载均衡,都是二次连接 可以通过对比源端口是否有改变来简单判断是一次连接还是二次连接,端口没改变,可以理解为一次连接,有改变就是二次连接 方法1: L3的一次连接模式 介绍:是指在网络层不对源IP做修改,直接将数据包转发...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7安装Docker,走上虚拟化容器引擎之路
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS8安装Docker,最新的服务器搭配容器使用
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7