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

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

2、用排序数组，寻找最大值元素容易，插入操作需移动很多元素。 使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。,4,定义4.1（Page 74） 一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。,堆的定义（二叉堆）,几乎完全二叉树（Page 71） 如果一棵二叉树，（在底层）除了最右边位置上的一个或几个叶子可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。, ,5,堆数据结构支持下列运算 DeleteMaxH：从一个非空堆H中，删除最大键值的数据项，并返回该数据； In

3、sertH,x：将数据项x插入堆H中； DeleteH,i：从堆中删除第i项； MakeHeapA：将数组转换为堆。,堆的蕴含特性： 沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。,6,堆的表示 有n个结点堆T，可以用一个数组H1.n用下面方式来表示： T的根结点存储在H1中； 设T的结点存储在Hj中，如果它有左子结点，则这个左子结点存储在H2j中；如果它还有右子结点，这个右子结点存储在H2j+1； 若元素Hj不是根结点，它的父结点存储在Hj/2中。 由 “几乎完全二叉树” 的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。 堆具有如下性质： key(Hj/2)key

4、(Hj) 2jn,7,201 17293 1041154657 3879510,堆和它的数组表示法 把存储在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按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,沿着每条从根到叶子的路径,元素的键值以降序排列。,8,4.2.1 堆上的运算,ShiftUp 假定对于某个i1，Hi的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为Shif

5、tUp的运算来修复堆。 ShiftUp运算沿着从Hi到根结点的惟一路径，把Hi移到适合它的位置上。在移动的每一步中，将Hi的键值与它的父结点Hi/2的键值相比较，若 若Hi Hi/2，则Hi和Hi/2互换（上移），继续。 若HiHi/2 或 i=1，终止。,9,H5=25和H2=17互换，H5=17, H2=25。,H10=25和H5=11互换，H10=11, H5=25。,201 1729 1011545 3751025,例，H10的键值由5变为25。,1 2 3 4 5 6 7 8 9 10,H2=25和H1=20互换，H2=20, H1=25。,10,过程 ShiftUp（参见Page

6、75） 输入：数组H1.n和索引i（1in） 输出：上移Hi(如果需要)，使它不大于父结点。 0. procedure ShiftUp(H1.n,i) 1.donefalse 2.if i=1 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 11. end procedure,11,ShiftDown 假定对于某个i n/2，Hi的键值变成小于它的左右子结点H2i或H2i+1 的键值，这样违反了堆的特

7、性，需使用称为ShiftDown的运算来修复堆。 ShiftDown运算使Hi下移到二叉树中适合它的位置上。在下移的每一步中，将Hi的键值与它的子结点键值相比较，若 Hi子结点键值，则Hi与子结点键值中较大者交换（下移），继续； Hi子结点键值 或 in/2，终止。,说明1：Hi应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。,173 1011,11 103,12,说明：若i n/2，则该结点位于叶子的位置，无需下移。, , ,n/2 = 15/2=7,n/2 = 10/2= 5,13,201 17239 1011545 37510,H2=3和

8、H5=11互换，H2=11, H5=3。,例，H2的键值由17变为3。,1 2 3 4 5 6 7 8 9 10,H5=3和H10=5互换， H5=5, H10=3。,14,过程 ShiftDown（Page 76） 输入：数组H1.n和索引i（1in） 输出：下移Hi(如果需要)，使它不小于子结点。 0. procedure ShiftDown(H1.n,i) 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 /

9、若有右子结点，选择子结点较大者。 7. end if 8. if key(Hi/2) n or done 14. end procedure,15,插入 为了把元素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),16,删除 要从大小为n的堆中删除元素Hi，可先用H

10、n替换Hi，然后将堆的大小减1。设原Hi的键值为key(x)，原Hn的键值为key(y)， 若key(y)key(x)，则执行上移y。 若key(y)key(x)，则执行下移y。 若i=1，则表示删除堆的最大值。,由于堆树的高度为 log2n，所以删除一个元素所需的时间为O(log2n)。,17,算法4.2 Delete（Page 77） 输入：非空堆H1.n和索引i（1in） 输出：删除Hi的新堆H1.n-1 1.xHi : yHn/Hi为要删除的元素 2.nn-1 3.if i=n+1 then exit /删除堆最后一个元素 4.Hiy 5.if key(y)key(x) then 6.

11、ShiftUp(H,i) 7.else 8.ShiftDown(H,i) 9.end if,18,创建堆 方法一 给出有n个元素的数组A1.n，要创建一个包含这些元素的堆可以这样进行： 首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。 插入第i个元素,上移次数（循环次数）最多为log2i，因此采用这种方法创建堆的时间复杂性为O(nlog2n)。,算法 MakeHeapByInsert（参见Page 77） 输入：n个元素的数组A1.n 输出：堆A1.n 1.for i=2 to n 2.ShiftUp(A,i) 3.end for,19,方法二 设数组A有n=10个元素，构

12、造它的几乎完全二叉树T。如下所示：,41 3283 104115136 77 3081792610,1 2 3 4 5 6 7 8 9 10,显然T不是堆。观察数组A的下列元素： An/2+1=A6=13，An=A10=26。 它们对应于T的叶子。这样调整可以从内部结点开始，先调整An/2=A5=11， 随后调整An/2-1= A4=10， ，直至A1=4。,20,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

13、,几乎完全二叉树的变化详见黑板,21,算法 MakeHeap (Page 79) 输入：n个元素的数组A1.n 输出：堆A1.n 1.for i= n/2downto 1 2.ShiftDown(A,i) 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),22,第0层结点下移最多次数20(k-0),令k=log2n，

14、设n=31则k=4。,第1层结点下移最多次数21(k-1),第i层结点下移最多次数2i(k-i),第k-1层结点下移最多次数2i(k-(k-1)=2i(1),第k层结点下移最多次数2i(k-k)=2k(0),设树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),第2层结点下移最多次数22(k-2),23,可参考本书 Page 50（式2.1

15、4）,24,定理4.1（Page 79） 使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么 n-1C(n) 4n 因此构造一个n元素的堆，算法MakeHeap需要(n)时间和(1)空间。,在过程ShiftDown的每一次循环中，最多有二次元素比较（有二个if语句），因此元素总的比较次数上界为4n（2*2n）。同时，过程ShiftDown至少执行一次循环，所以元素的最少比较次数由内部结点数（或叶子数）决定，元素总的比较次数下界为2 n/2n-1。,25,4.2.3 堆排序,给定数组A1.n，设每个元素的键值是该元素本身，可采用如下方法进行排序： 使用算法Ma

16、keHeap将数组A变换成堆。 首先将A1和An交换，显然An为数组中最大元素，然后调用过程ShiftDown将A1.n-1转换成堆。 接着将A1和An-1交换，显然An-1为数组中次最大元素，然后调用过程ShiftDown将A1.n-2转换成堆。 交换元素和堆调整过程一直重复，直至堆的大小为1。,26,算法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)时

17、间， ShiftDown运算用O(log2n)时间，并且重复n-1次。,27,这个算法在原有空间进行排序，建立堆用(n)时间， ShiftDown运算用O(log2n)时间，并且重复n-1次，显然建立堆所用的时间为低次项，可略。 定理4.2(Page 80) 算法HeapSort对n个元素排序，需要用O(nlog2n)时间和(1)空间。 由此可见，堆排序是最优秀的排序算法。 4.2.4 最大堆和最小堆 最大堆：最大键值元素存放在根结点。 最小堆：最小键值元素存放在根结点。,28,4.3 不相交集数据结构,不相交集合及运算 假设给出一个有n个元素的集合S，这些元素被分成若干个不相交集合，最初假设

18、每个元素自成一个集合。经n次合并（Union）和寻找（Find）后，构成若干个不相交子集，每个子集用该子集中一个特殊元素命名。显然合并次数最多为n-1次。 例： 假定元素是整数1,2,3,4 集合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,4,8,9 4个子集依次被命名为1、3、8、9。,29,我们对Union和Find二种不相集运算定义如下： Find(x)：寻找并返回包含元素x的集合名字。 Union(x,y)：

19、将包含元素x和y的二个集合用它们的并集替换。并集的名字，或为包含元素x的那个集合的名字，或为包含元素y的那个集合的名字。 我们目的是设计这二种运算的有效算法，为此需要一种数据结构，它既要简单，又要有效实现合并和寻找这二种运算。,30,不相交集数据结构 将用于命名子集的元素视为根，其余元素视为其后代，每个子集可用一棵根树来表示，这样便形成了森林。,9,除根结点外，每个结点都有一个指针指向父结点。根结点用作集合的名字。根结点的指针值为0，表示不指向任何结点。 森林可方便地用数组A1.n，Aj是j的父结点，Aj=0表示j是根结点。 对于任一元素x，用root(x)表示包含x的树的根，例root(6)

20、=3。,1 2 3 4 5 6 7 8 9 10 11,8,4,1,7,10,11,3,2,5,6,31,不相交集运算实现 Find(x) 寻找并返回包含元素x的树的根。例， Find(6)=root(6)=3 Union(x,y) 将包含x和y的二个不相交集合并成一个集合。也就是说把二棵树合并成一棵树。树的根分别为root(x)或root(y)，对于任意二个元素x和y，Union(x,y)实际上应表示为Union(root(x),root(y) 合并后根为root(x)，即Aroot(y)root(x)。 合并后根为root(y)，即Aroot(x)root(y)。,8 4,9,8 49,或

21、,9 8 4,例，Union(4,9)=Union(root(4),root(9)=Union(8,9),32,4.3.1 按秩合并措施,n n-1 2 1, 问题的提出 若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。 假定从单元素集合1,2, ,n开始，执行下面的合并序列（假设第二个参数为合并后树的根）： Union(1,2),Union(2,3), ,Union(n-1,n) 形成的树如左图所示。 执行下面的寻找序列： Find(1),Find(2), ,Find(n) n次寻找运算总的代价为：,33,引入秩 为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个

22、非负数作为该结点的秩（记为rank），初始时每个结点的秩均为0。 设x和y是二棵不同树的根，执行Union(x,y)时，比较rank(x)和rank(y)，若 rank(x)rank(y)，则使x成为y的父结点， rank(x)和rank(y)不变。,34,x1,100,y2,21,50,60,y1,100,x2,21,50,60,71,100,y2,21,50,60,x2,rank(x)rank(y)，则使y成为x的父结点， rank(x)和rank(y)不变。,rank(x)=rank(y)，则使y成为x的父结点，rank(y) 增1，rank(x)不变（或相反）。,rank(x)rank

23、(y)，则使x成为y的父结点， rank(x)和rank(y)不变。,y3,35,令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。,观察结论4.1(Page 82) rank(p(x)rank(x),观察结论4.2(Page 82) rank(x)的值初始化为0，在后继合并运算序列中递增，直到x不是根结点。一旦x变成了其它树的子结点，它的秩就不再改变。,36,4.3.3 Union-Find算法,算法4.6 Find（参见Page 83) 输入：结点x 输出：root(x)，包含x的树的根。 0. procedure Find(x) 1.yx 2.while p(y) 0 3.y

24、p(y) 4.end while 5.rooty 6.return root 7. end procedure/注：路径压缩被略去,37,算法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)u /包含x的树的根结点u是合并后的根结点 9.end if 10. end procedure,38,设S=1,2,3,4,5,6,7,8,9，初始时每棵树由单个元素构成，这样森林共由9棵树构成，上标表示秩rank（若为0，在后面的