第四章堆和不相交集数据结构

算法设计与分析

AlgorithmsDesignandAnalysis

赵廷刚兰州城市学院数学学院2013.3本章内容4.1引言4.2堆(heaps)4.2.1堆上的运算4.2.2创建堆4.2.3堆排序4.2.4最小堆和最大堆4.3不相交集数据结构(disjointsetsdatastructures)4.3.1按秩合并措施4.3.2路径压缩4.3.3UNION-FIND算法4.3.4UNION-FIND算法分析

数据结构(datastructure)是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。

4.1引言常见数据结构：数组(array)、列表(list)、堆栈(stack)、队列(queue)、链表(linkedlist)、树(tree)、图(graph)、堆(heap)、散列(hash)4.2堆（heaps）在许多算法中，需要支持两种运算的数据结构：插入元素和寻找最大值元素。支持这两种运算的数据结构称为优先队列。如果使用普通队列，那么寻找最大元素需要搜索整个队列，开销比较大；如果采用排序数组，那么插入运算就需要移动很多元素，开销也会较大。优先队列的有效实现是使用“堆”的简单数据结构。一个（二叉）堆是一个几乎完全的二叉树，它的每个节点都满足堆的特性：如果v和p(v)分别是节点和它的父节点，那么存储在p(v)中的数据项键值不小于存储在v中的数据项键值。定义4.1堆数据结构支持下面的运算：delete-max[H]:从堆H中删除最大键值的数据项并将数据项返回。insert[H,x]:插入项x到堆H中。delete[H,i]:从堆H中删除第i项。makeheap[A]:将数组A转换成堆。堆的例子/view/4147d863caaedd3383c4d3c6.html注意：如果堆中的节点有右子节点，则它一定也有左子节点。堆可以看做是二叉树，而它实质上是一个数组H[1…n]。它有如下性质：/p-240830965233.html4.2.1堆上的运算----sift-up假设对某个i>1,H[i]变成了键值大于它的父节点键值的元素，这样就违反了堆性质，因此该数据结构就不再是堆了，如果要修复它成为堆，就用sift-up的运算.算法描述：Sift-up运算沿着从H[i]到根节点的唯一一条路径，把H[i]移到适合它的位置上。在沿着路径的每一步上，都将H[i]键值与它的父节点的键值相比较。4.2.1堆上的运算----sift-down假设对i≤floor(i/2),存储在H[i]中元素的键值变成小于H[2i]和H[2i+1]中的最大值，这样也违反了堆性质，因此该数据结构就不再是堆了，如果要修复它成为堆，就用sift-down的运算.算法描述：Sift-down运算使H[i]“渗”到二叉树中适合它的位置上，沿着路径的每一步上，都将H[i]键值与存储在它的子节点（如果有）的两个（可能是一个）键值里最大的那个相比较。4.2.1堆上的运算----插入（insert）插入：为了把元素x插入到堆H中，先将堆大小加1，然后将x添加到H的末尾，再根据需要，将x上移，直到满足堆性质.4.2.1堆上的运算----删除（delete）删除：要从大小为n的堆H中删除元素H[i]，可先用H[n]替换H[i],然后将堆栈大小减1，如果需要的话，根据H[i]的键值与存储在它的父节点和子节点中元素键值的大小，对H[i]做sift-up或sift-down运算，直到满足堆性质.4.2.1堆上的运算----删除最大值（delete-max）删除最大值：要从大小为n的堆H中删除元素H[i]，可先用H[n]替换H[i],然后将堆栈大小减1，如果需要的话，根据H[i]的键值与存储在它的父节点和子节点中元素键值的大小，对H[i]做sift-up或sift-down运算，直到满足堆性质.4.2.2堆上的运算----创建堆（makeheap）创建堆：给出一个有n个元素的数组A[1…n]，将该数组变成一个几乎完全的二叉树，并把这个二叉树转换成一个堆。从最后一个节点开始(编码为n的节点)到根节点(编码为1的节点)，逐个扫描，根据需要每次将当前节点为根的子树转换为堆。例4.34.2.3堆排序算法描述：给出数组A[1…n]，首先将它转换为堆，由于最大值在A[1]中，所以将A[1]和A[n]互换，这样A[n]中存放了最大值，接下来考虑数组A[1…n-1]，它可能不是堆，利用sift-down运算将A[1…n-1]转换成堆，再将A[1]和A[n-1]互换，如此下去，直到堆的大小变为1，即可。4.3不相交集数据结构假设有一个包含n个元素的集合S,它被分成不相交的一些子集，每个子集用其中的一个元素做名字或代表。例如：S={1,2,……,11},子集合为{1,7,10,11},{2,3,5,6},{4,8},{9}这4个子集合被依次命名为1,3,8,9.FIND(x):返回包含x的子集合的名字。UNION(x,y)：将包含x的子集合与包含y的子集合合并，得到的并集的名字取原来两个子集合的名字之一。根树表示法：用根树表示每个子集合，子集合中的元素存储在节点中，树中除根节点外的每一个元素x都有一个指向父节点p(x)的指针.根有一个空指针，用作集合的名字或代表。这些根树在一起组成一个森林。对于任意元素x，用root(x)表示包含x的树的根。那么，FIND(x)总是返回root(x)。由于合并运算必须有两棵树的根作为它的参数，我们将假定对于任意两个元素x和y,UNION(x,y)实际上是表示UNION(root(x),root(y)).在进行FIND(x)运算时，只是沿着从x开始直到根节点的路径，然后返回root(x)。在进行UNION(x,y)运算时，令root(x)的链接指向root(y)，也就是说，如果root(x)是u，root(y)是v,就令v是u的父节点.一个极端例子：假设集合S={1,2,…,n}，它的子集合为：{1},{2},…,{n}.执行n-1个合并运算：UNION{1,2},UNION{2,3},…,UNION{n-1,n}之后的结果见图4.6(a)，这是一个高度为n-1的树。如果接下来要执行寻找运算：FIND(1),FIND(2),…,FIND(n),则n次寻找的总代价为：这是很耗费时间的，为了克服这个弊端，采用：按秩合并措施和路径压缩措施。4.3.1按秩合并措施为了限制每棵树的高度，采用按秩合并措施：给每个节点存储一个非负数作为该节点的秩，记为rank,节点的秩基本上就是它的高度。设x和y是当前森林中两棵不同的根树的根，初始状态时，每个节点的秩是0，在执行运算UNION(x,y)时，比较rank(x)和rank(y),如果rank(x)<rank(y),就使y为x的父节点；如果rank(x)>rank(y),就使x为y的父节点；如果rank(x)=rank(y),就使y为x的父节点,并rank(y)加1.那个极端例子：按照上述规则之后的结果见图4.6(b)，这是一个高度为1的树。如果接下来要执行寻找运算：FIND(1),FIND(2),…,FIND(n),则n次寻找的总代价为：n