第4章 堆和不相交数据结构.ppt

1、1,第4章 堆和不相交集数据结构,2,二叉树性质 (Page 71) 性质1：在二叉树中，第j层的顶点数最多是2j。 性质2：令二叉树T顶点数是n，高度是k，那么 如果T是完全的，等号成立。如果T是几乎完全的，那么 性质3：有n个顶点的完全或几乎完全的二叉树的高度是 性质4：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1,性质：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1,证明：n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点

2、都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,4,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in) ，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2 (2) 如果2in，则结点i无左孩子；如果2in ，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1n ，则其右孩子是2i+1,5,4.1 引言（堆、不相交集） 4.2 堆 4.2.1 堆上的运算 4.2.2 创建堆 4.2.

3、3 堆排序 4.2.4 最大堆和最小堆 4.3 不相交集数据结构 4.3.1 按秩合并措施 4.3.3 Union-Find算法 4.3.2 路径压缩 4.3.4 Union-Find算法的分析（略）,6,4.2 堆,堆的引入 在许多算法中，需要支持下面二种运算： 插入元素 寻找最大值元素（或最小值元素） 支持这二种运算的数据结构称为优先队列。,可采用下述三种方法实现优先队列： 使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。 使用排序数组，寻找最大值元素容易，插入操作需移动很多元素。 使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。,7,定义4.1（P

4、age 74） 一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。,堆的定义（二叉堆）,几乎完全二叉树（Page 71） 如果一棵二叉树，除了最右边位置上的一个或几个叶子可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。, ,几乎完全二叉树例,8,堆数据结构支持下列运算 DeleteMax(H)：从一个非空堆H中，删除最大键值的数据项，并返回该数据； Insert(H,x)：将数据项x插入堆H中； Delete(H,i)：从堆中删除第i项； MakeHeap(A)：将数组转

5、换为堆。,堆的蕴含特性： 沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。,9,堆的表示 有n个结点堆T，可以用一个数组H1.n用下面方式来表示： T的根结点存储在H1中； 设T的结点存储在Hj中，如果它有左子结点，则这个左子结点存储在H2j中。如果它还有右子结点，这个右子结点存储在H2j+1； 若元素Hj不是根结点，它的父结点存储在Hj/2中。 由 “几乎完全二叉树” 的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。 堆具有如下性质： key(Hj/2)key(Hj) 2jn,10,201 17293 1041154657 3879510,堆和它的数组表示法 把存储

6、在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按1到n”的顺序进行编号，那么数组元素Hi对应树中编号为i的结点。,1 2 3 4 5 6 7 8 9 10,H2=17的左子结点为H2*2=H4=10 H2=17的右子结点为H2*2+1=H5=11 H9=7的父结点为H 9/2 =H4=10,沿着每条从根到叶子的路径，元素的键值以降序排列。,11,4.2.1 堆上的运算,ShiftUp 假定对于某个i1，Hi的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为ShiftUp的运算来修复堆。 ShiftUp运算沿着从Hi到根结点的惟一路径，把Hi移到适合它的位置上。在移动

7、的每一步中，将Hi的键值与它的父结点Hi/2的键值相比较，若 若HiHi/2，则Hi和Hi/2互换（上移），继续。 若HiHi/2 或 i1，终止。,12,H5=25H2=17，互换。互换后H5=17、H2=25；,H10=25H5=11，互换。互换后H10=11、H5=25；,H10的键值由5变为25,1 2 3 4 5 6 7 8 9 10,H2=25H1=20，互换。互换后H2=20、H1=25；,201,172,9,104,115,510,4,5,3,7,H1=25位于根结点。此时i=1，程序终止。,2510,13,过程 ShiftUp（参见Page 75） 输入：数组H1.n和索引i

8、（1in） 输出：上移Hi(如果需要)，使它不大于父结点。 1.donefalse 2.if i1 then exit/根结点 3.repeat 4. if key(Hi)key(Hi/2) then 5.互换Hi和Hi/2 6. else 7.donetrue 8. end if 9. i i/2 10.until (i=1) or done,14,ShiftDown 假定对于某个i n/2（非叶结点），Hi的键值变成小于它的左右子结点H2i或H2i+1 的键值，这样违反了堆的特性，需使用称为ShiftDown的运算来修复堆。 ShiftDown运算使Hi下移到二叉树中适合它的位置上。在下移

9、的每一步中，将Hi的键值与它的子结点键值相比较，若 Hi子结点键值，则Hi与子结点键值中较大者交换（下移），继续； Hi子结点键值 或 in/2，终止。,说明：Hi应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。,17 1011,11 103,3,15,说明：若in/2，则该结点位于叶子的位置，无需下移。, , ,n/2 = 15/2=7,n/2 = 10/2= 5,16,H2键值由17变为3,1 2 3 4 5 6 7 8 9 10,H5=3小于H10=5，所以H5和H10互换。交换后H5=5，H10=3；,H10=3位于叶结点位置。 i=1

10、0n/2=5，程序终止。,H2=3小于H4和H5，因为H4H5，所以H2和H5互换。交换后H2=11，H5=3；,201,172,93,104,115,4,5,3,7,5,32,17,过程 ShiftDown（Page 76） 输入：数组H1.n和索引i（1in） 输出：下移Hi（如果需要），使它不小于子结点。 1.donefalse 2.if 2in then exit/Hi是叶结点，无需下移。 3.repeat 4. i2i /i指向子结点 5. if (i+1n) and (key(Hi+1)key(Hi) then 6. ii+1 /若有右子结点，选择子结点较大者。 7. end if

11、 8. if key(Hi/2)n) or done,18,插入 为了把元素x插入堆H中，先将堆的大小增1，然后元素x添加到H的末尾，再根据需要将x上移，直到满足堆的特性。若新堆的个数为n，那么堆树的高度为 log2n 所以将一个元素插入大小为n的堆中所需要的时间为 O(log2n),算法4.1 Insert（Page 76-77） 输入：堆H1.n和元素x 输出：新堆H1.n+1，x为其元素之一。 1.nn+1 2.Hnx 3.ShiftUp(H,n),19,删除 要从大小为n的堆中删除元素Hi，可先用Hn替换Hi，然后将堆的大小减1。设原Hi的键值为key(x)，原Hn的键值为key(y)

12、， 若key(y)key(x)，则执行上移y。 若key(y)key(x)，则执行下移y。 若i=1，则表示删除堆的最大值。,由于堆树的高度为 log2n，所以删除一个元素所需的时间为O(log2n)。,20,算法4.2 Delete（Page 77） 输入：非空堆H1.n和索引i（1in） 输出：删除Hi的新堆H1.n-1 1.xHi : yHn/Hi为要删除的元素 2.nn-1 3.if in+1 then exit /删除堆最后一个元素 4.Hiy 5.if key(y)key(x) then 6.ShiftUp(H,i) 7.else 8.ShiftDown(H,i) 9.end if

13、,21,4.2.2 创建堆 方法一 给出有n个元素的数组A1.n，要创建一个包含这些元素的堆可以这样进行： 首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。 插入第i个元素，上移次数(循环次数)最多为log2i，因此采用这种方法创建堆的时间复杂性为O(nlog2n)。,算法 MakeHeapByInsert（参见Page 77） 输入：n个元素的数组A1.n 输出：堆A1.n 1.for i2 to n 2.ShiftUp(A,i) 3.end for,22,4.15 给出一个整数数组A1.n，可按照下面的方法建立一个A的堆B1.n。从空堆开始，反复将A中元素插入B，每一次

14、调整当时的堆，直到B包含A中的所有元素。证明在最坏情况下，算法运行时间是(nlogn)。 解： 1.for i1 to n 2.BiAi 3.ShiftUp(B,i) /ShiftUp(B1.i,i) 4.end for 在最坏情况下,23,4.16 用图说明练习4.15的算法对于下面数组的运算。 解： A1.8 ,B1.1=,B1.8=,B1.2=,B1.3=,B1.4=,B1.5=,B1.7=,B1.6=,24,方法二 设数组A有n=10个元素，构造它的几乎完全二叉树T，如下所示，显然T不是堆。,1 2 3 4 5 6 7 8 9 10,观察数组A的元素：An/2+1=A6，An=A10，

15、它们对应于T的叶子。这样调整可以从内部结点开始，先调整An/2=A5， 随后调整An/2-1=A4 ， ，直至A1。,41,32,83,104,115,136,77,308,179,2610,25,41 32 83 104 115136 77 308 179 2610,1 2 3 4 5 6 7 8 9 10,An/2=A5=11 An/2-1=A4=10 An/2-2=A3=8 An/2-3=A2=3 An/2-4=A1=4,26,算法 MakeHeap (Page 79) 输入：n个元素的数组A1.n 输出：堆A1.n 1.for in/2 downto 1 2.ShiftDown(A,i

16、) 3.end for,设树T的高度为k=log2n，令Aj为对应于树的第i层中的第j个结点，执行ShiftDown(A,j)运算，下移次数(即循环次数)最多为k-i。因为在第i层恰好有2i个结点，故执行总的下移次数的上界为： 20(k-0)+21(k-1)+22(k-2)+ +2k-3(3) +2k-2(2) +2k-1(1),27,第0层结点下移最多次数20(k-0),令k=log2n，设n=31则k=4。,第1层结点下移最多次数21(k-1),第i层结点下移最多次数2i(k-i),第k-1层结点下移最多次数2k-1(k-(k-1)=2k-1(1),设树T的高度为klog2n，令Aj为对应

17、于树的第i层中的第j个结点，执行ShiftDown(A,j)运算，下移次数(即循环次数)最多为k-i。因为在第i层恰好有2i个结点，故执行总的下移次数的上界为: 20(k-0)+21(k-1)+22(k-2)+ +2k-3(3) +2k-2(2) +2k-1(1),第2层结点下移最多次数22(k-2),28,可参考本书 Page 50（式2.14）,29,定理4.1（Page 79） 使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么 n-1C(n)4n 因此构造一个n个元素的堆，算法MakeHeap需要(n)时间和(1)空间。,在过程ShiftDown的每

18、一次循环中，最多有二次元素比较（有二个if语句），因此元素总的比较次数上界为2*2n。同时过程ShiftDown至少执行一次循环，所以元素的最少比较次数由内部结点数决定，元素总的比较次数下界为2n/2n-1（若原为堆）。,30,4.2.3 堆排序,给定数组A1.n，设每个元素的键值是该元素本身，可采用如下方法进行排序： 使用算法MakeHeap将数组A变换成堆。 首先将A1和An交换，显然An为数组中最大元素，然后调用过程ShiftDown将A1.n-1转换成堆。 接着将A1和An-1交换，显然An-1为数组中次最大元素，然后调用过程ShiftDown将A1.n-2转换成堆。 交换元素和堆调整

19、过程一直重复，直至堆的大小为1。,31,算法4.5 HeapSort(Page 80) 输入：n个元素的数组A 输出：数组A中元素按升序排列 1.MakeHeap(A) 2.for jn downto 2 3.互换A1和Aj 4.ShiftDown(A1.j-1,1) 5.end for,这个算法在原有空间进行排序，建立堆用(n)时间， ShiftDown运算用O(log2n)时间，并且重复n-1次。,参考习题4.14,32,这个算法在原有空间进行排序，建立堆用(n)时间， ShiftDown运算用O(log2n)时间，并且重复n-1次，显然建立堆所用的时间为低次项，可略。 定理4.2(Pag

20、e 80) 算法HeapSort对n个元素排序，需要用O(nlog2n)时间和(1)空间。 由此可见，堆排序是最优秀的排序算法。 4.2.4 最大堆和最小堆 最大堆：最大键值元素存放在根结点。 最小堆：最小键值元素存放在根结点。,33,4.3 不相交集数据结构（并查集）,是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。如数据结构课中讲到的最小生成树Kruskal算法： Kruskal是一种贪心算法，比较适用于稀疏图:为使生成树上边的权值和最小，则应使生成树中每一条边的权值尽可能地小。 具体做法:找出森林中连接任意两棵树的所有边中，具有最小权值的边，如

21、果将它加入生成树中不产生回路，则它就是生成树中的一条边。这里的关键就是如何判断将它加入生成树中不产生回路。,34,4.3 不相交集数据结构,不相交集合及运算 设集合S有n个元素，这些元素被分成若干个不相交子集。最初假设每个元素自成一个集合，这样共有n个子集。经n次合并（Union）后，构成若干个不相交子集。每个子集用该子集中一个特殊元素命名。 例：假定n个元素的集合S=1,2,3,4,5,6,7,8,9,10,11 最初有11个子集 1,2,3,4,5,6,7,8,9,10,11 每个子集的名称分别为子集中元素本身。 经若干次合并后，形成4个子集，假设它们是 1,7,10,11,2,3,5,6

22、,4,8,9 4个子集依次被命名为1、3、8、9。,35,我们对Union和Find二种不相集运算定义如下： Find(x)：寻找并返回包含元素x的集合名字。 Union(x,y)：将包含元素x和y的二个集合用它们的并集替换。并集的名字，或为包含元素x的那个集合的名字，或为包含元素y的那个集合的名字。 我们目的是设计这二种运算的有效算法，为此需要一种数据结构，它既要简单，又要能有效实现合并和寻找这二种运算。,36,不相交集数据结构 将用于命名子集名称的元素视为根，其余元素视为其后代，每个子集可用一棵根树来表示，这样便形成了森林。,9,每个结点都有一个指针。非根结点的指针指向它的父结点；根结点的

23、指针值为0，表示不指向任何结点。 根结点用作集合的名字。 森林可方便地用数组A1.n。Aj是j的父结点，若Aj=0，说明j是根结点。 对于任一元素x，用root(x)表示包含x的树的根，例root(6)=3。,1 2 3 4 5 6 7 8 9 10 11,8,4,1,7,10,11,3,2,5,6,37,不相交集运算实现 Find(x) 寻找并返回包含元素x的树的根。例， Find(6)=root(6)=3 Union(x,y) 将包含x和y的二个不相交集合并成一个集合，也就是说把二棵树合并成一棵树，Union(x,y)可表示为Union(root(x),root(y)。 若合并后树的根为r

24、oot(x)，则有Aroot(y)=root(x)。 若合并后树的根为root(y)，则有Aroot(x)=root(y)。,8 4,9,8 49,或,9 8 4,例，Union(4,9)=Union(root(4),root(9)=Union(8,9),1 2 3 4 5 6 7 8 9 10 11,8,38,4.3.1 按秩合并措施,n n-1 2 1, 问题的提出 若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。 假定从单元素集合1,2, ,n开始，执行下面的合并序列（假设第二个参数为合并后树的根）： Union(1,2),Union(2,3), ,Union(n-1

25、,n) 形成的树如左图所示。 执行下面的寻找序列： Find(1),Find(2), ,Find(n) n次寻找运算总的代价为：,39,引入秩 为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个非负数作为该结点的秩（记为rank），初始时每个结点的秩均为0。 设x和y是二棵不同树的根，执行Union(x,y)时，比较rank(x)和rank(y)，若 rank(x)rank(y)，则使x成为y的父结点， rank(x)和rank(y)不变。,40,x1,100,y2,21,50,60,y1,100,x2,21,50,60,71,100,y2,21,50,60,x2,rank(x)ran

26、k(y)，则使y成为x的父结点， rank(x)和rank(y)不变。,rank(x)=rank(y)，则使y成为x的父结点，rank(y) 增1，rank(x)不变（或相反）。,rank(x)rank(y)，则使x成为y的父结点， rank(x)和rank(y)不变。,y2,41,令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。 观察结论4.1(Page 82) rank(p(x)rank(x) 观察结论4.2(Page 82) rank(x)的值初始化为0，在后继合并运算序列中递增，直到x不是根结点。一旦x变成了其它树的子结点，它的秩就不再改变。,42,4.3.3 Union

27、-Find算法,算法4.6 Find（参见Page 83) 输入：结点x 输出：root(x)，包含x的树的根。 0. procedure Find(x) 1.yx 2.while p(y)0/p(y)=0表示y是根结点 3.yp(y) 4.end while 5.rooty 6.return root 7. end procedure/注：路径压缩被略去,43,算法4.7 Union(Page 83) 输入：结点x和y 输出：包含x和y的二棵树的合并 0. procedure Union(x,y) 1.uFind(x) : vFind(y) 2.if rank(u)rank(v) then 3.p(u)v /包含y的树的根结点v是合并后的根结点 4.if rank(u)=rank(v) then 5.rank(v)=rank(v)+1 6.end if 7.else /rank(u)rank(v) 8.p(v