《算法导论》学习总结 — 第21章 用于不相交集合的数据结构

并查集(Disjoint Set)

起因:在某些应用中,要将n个不同的元素分成一组不相交的集合。

 

第21.1节 不相交集合的链表表示有些不太明白,有达人讲解或贡献出自己的学习笔记????

启发式策略是什么?—>我对这个概念一直很好奇???但是一直找不到好的文章和解释,看到我文章的朋友,求推荐,谢谢。

 

21.3节 不相交集合森林

这个曾经写过一个模板,书看了后,基本都可以写出来吧,依葫芦画瓢,代码模板链接:

http://www.wutianqi.com/?p=1066

至于两种启发式策略,来分别说下其作用:

①.按秩合并(union by rank),把较少结点的树的根合并到较多结点的树的跟,这样是为了尽量使树的高度减小,因此,可以优化Find_Set(x)。(看Find_Set()函数的代码~~)

②.路径压缩(path compression),使查找路径上的每个结点都指向根节点,路径压缩并不改变结点的秩,而且这样也同样优化了Find_Set(x)。

 

完毕!

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — 第21章 用于不相交集合的数据结构》有616个想法

  1. 我觉得启发式策略,指的是根据现有的一些条件,通过总结规律,或者其它一些手段来解决问题。应该没有一个什么严格的概念。
    比方在哈希表中CLRS说,乘法哈希函数和除法哈希函数是启发式函数,而全域哈希运用的是随机策略。可见随机肯定不能叫启发,另外从它的名字启发(heuristic),我猜测应该就是说的,通过一些点(条件),来点拨出解决问题的方法就叫启发。
    当然这只是我个人的理解。

发表评论

电子邮件地址不会被公开。 必填项已用*标注