chapter 2 堆和不相交集数据结构

1、School of Software, YunNan University堆和不相交集数据结构2HeJing(2011) School of Software Outline1.堆的定义堆的定义2.堆上的运算堆上的运算3.堆排序堆排序4.最小堆和最大堆最小堆和最大堆3HeJing(2011) School of Software2.1 2.1 堆的定义堆的定义p在许多算法中，需要支持下面两种运算的数据结在许多算法中，需要支持下面两种运算的数据结构：插入元素和寻找最大值构：插入元素和寻找最大值n普通队列：只能在队尾插入元素，但寻找最大元需要普通队列：只能在队尾插入元素，但寻找最大元需要搜索整个队

2、列搜索整个队列2022-3-22 A BCDE队头队头队尾队尾队列队列4HeJing(2011) School of Software2.1 2.1 堆的定义堆的定义p在许多算法中，需要支持下面两种运算的数据结在许多算法中，需要支持下面两种运算的数据结构：插入元素和寻找最大值构：插入元素和寻找最大值n排序数组：寻找最大元非常简单，但插入运算需要移排序数组：寻找最大元非常简单，但插入运算需要移动很多元素动很多元素 堆堆2022-3-22 3024201251821635HeJing(2011) School of Software2.1 2.1 堆的定义堆的定义p堆的定义堆的定义：一个（二叉树）

3、堆是一个几乎完全的二叉树，：一个（二叉树）堆是一个几乎完全的二叉树，它的每个节点都满足堆的特性：如果它的每个节点都满足堆的特性：如果v和和p(v)分别表示节分别表示节点和它的父节点，那么存储在点和它的父节点，那么存储在p(v)中的数据项键值不小中的数据项键值不小于存储在于存储在v中数据项的键值。中数据项的键值。 2022-3-22 302420125182163蕴涵：沿着每条从根到叶子的路径，蕴涵：沿着每条从根到叶子的路径，元素的键值以非升序排列。元素的键值以非升序排列。6HeJing(2011) School of Software2.1 2.1 堆的定义堆的定义p堆的表示堆的表示：一个有：

4、一个有n个节点的堆，可以用一个一维数组个节点的堆，可以用一个一维数组H1n来表示。来表示。nT的根节点存储在的根节点存储在H1中；中；n假设假设T的节点的节点x存储在存储在Hj中，中，则它的左孩子存储在则它的左孩子存储在H2j中，中，它的右孩子存储在它的右孩子存储在H2j+1中；中；n元素元素Hj的父节点如果不是根节点，的父节点如果不是根节点，则存储在则存储在H 2022-3-22 3024201251821631234567892/ j3024182021631257HeJing(2011) School of Software2.1 2.1 堆的定义堆的定义p如果堆中的节点有右子节点，则它

5、一定有左子节点如果堆中的节点有右子节点，则它一定有左子节点p堆的表现是一棵二叉树，但它的数据结构实质是一个一维堆的表现是一棵二叉树，但它的数据结构实质是一个一维数组数组p对于任何索引对于任何索引j，2=j=Hj 2022-3-22 2/ j8HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pdeletemaxH：从一个非空堆：从一个非空堆H中删除最大键值，中删除最大键值，并返回该值并返回该值pinsertH,x：将：将x插入堆插入堆H中中pdeleteH,i：从堆：从堆H中删除第中删除第i项项pmakeheapA：将数组：将数组A转换成堆转换成

6、堆 2022-3-22 9HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算p两个辅助运算两个辅助运算Sift_up和和Sift_downn过程：过程：Sift_up（元素上移）（元素上移）n输入：数组输入：数组H1n和位于和位于1和和n之间的索引之间的索引in输出：上移输出：上移Hi，以使，以使H满足堆的定义满足堆的定义1.donefalse;2.if i=1 then exit;3.repeat4. if HiH 5. then 交换交换Hi与与H 6. else done true; 7. i ;8.until i=1 or done 20

7、22-3-22 3024201251821631302243184205216673812951035352/ i2/ i2/ i10HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算p两个辅助运算两个辅助运算Sift_up和和Sift_downn过程：过程：Sift_down（元素下移）（元素下移）n输入：数组输入：数组H1n和位于和位于1和和n之间的索引之间的索引in输出：上移输出：上移Hi，以使，以使H满足堆的定义满足堆的定义2022-3-22 152243184205216673812930302420125182163524201218

8、216311HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算p两个辅助运算两个辅助运算Sift_up和和Sift_downn过程：过程：Sift_down（元素下移）（元素下移）n输入：数组输入：数组H1n和位于和位于1和和n之间的索引之间的索引in输出：上移输出：上移Hi，以使，以使H满足堆的定义满足堆的定义1.donefalse;2.if 2in then exit;3.repeat4. i 2i;5. if i+1Hi then i i+1;6. if H n or done 2022-3-22 2/ i2/ i1522431842052

9、1667381293012HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pdeletemaxH：从一个非空堆：从一个非空堆H中删除最大键值，中删除最大键值，并返回该值并返回该值pinsertH,x：将：将x插入堆插入堆H中中pdeleteH,i：从堆：从堆H中删除第中删除第i项项pmakeheapA：将数组：将数组A转换成堆转换成堆 2022-3-22 13HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pinsertH,x：将：将x插入堆插入堆H中中n算法算法insertn输入：堆输入：堆H

10、1n和元素和元素xn输出：新的堆输出：新的堆H1n1.nn+1;2.Hn x;3.Sift_up(H,n) 2022-3-22 新堆中的元素个数新堆中的元素个数n，则堆的高度为则堆的高度为算法时间复杂度为：算法时间复杂度为：O(log n)nlog14HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pdeleteH,i：从堆：从堆H中删除第中删除第i项项n算法算法deleten输入：非空堆输入：非空堆H1n和位于和位于1和和n之间的索引之间的索引in输出：删除输出：删除Hi之后的新堆之后的新堆H1n-11.xHi; yHn;2.if i=n t

11、hen exit; 3.nn-1;4.Hi y;5.if y=x then Sift_up(H,i);6.else Sift_down(H, i);7.endif 2022-3-22 nlog302420125182163算法时间复杂度：算法时间复杂度：15HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pdeletemaxH：从一个非空堆：从一个非空堆H中删除最大键值，并返中删除最大键值，并返回该值回该值n算法算法deletemaxn输入：堆输入：堆H1nn输出：返回最大键值输出：返回最大键值x，并将其从堆中删除，并将其从堆中删除1.xH1;

12、2.delete(H,1);3.return x 2022-3-22 该算法的时间复杂度就该算法的时间复杂度就是删除算法的时间复是删除算法的时间复杂度：杂度： O(log n)16HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pmakeheapA ：将数组：将数组A转换成堆转换成堆n直接插入法直接插入法：从空堆开始，不断插入每一个元素，因为插入第：从空堆开始，不断插入每一个元素，因为插入第j个元素时，所需比较次数为个元素时，所需比较次数为log j，用这种方法建堆的复杂性是，用这种方法建堆的复杂性是O(nlog n) 2022-3-22 )l

13、og(log)log(log2log2)2log(22nloglog)log(logloglog112/11111nnjnnjnnnnnjnnOjnjnjnjnjnjnjnjnj同理得到：所以）（又即P5217HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pmakeheapA ：将数组：将数组A转换成堆转换成堆n利用二叉树的性质建堆利用二叉树的性质建堆：从第一个非叶节点开始判断该子树是：从第一个非叶节点开始判断该子树是否是一个堆，如果不是，则调用否是一个堆，如果不是，则调用Sift_down算法构造堆算法构造堆n算法：算法：MakeHeapn

14、输入：输入：n个元素的数组个元素的数组A1nn输出：输出：A1n转换成的堆转换成的堆1.for i downto 12. Sift_down(A, i);3.endfor 2022-3-22 2/n431030178111371423384105116137783091718HeJing(2011) School of Software2.2 2.2 堆上的运算堆上的运算pmakeheapA ：将数组：将数组A转换成堆转换成堆n利用二叉树的性质建堆利用二叉树的性质建堆：从第一个非叶节点开始判断该子树是：从第一个非叶节点开始判断该子树是否是一个堆，如果不是，则调用否是一个堆，如果不是，则调用Si

15、ft_down算法构造堆算法构造堆n假设堆的高为假设堆的高为k=|log n|nn=20+21+22+2k-1+r 2022-3-22 4310301781113714233841051161377830917nkikiiikkkiikkkiikiikiki2)2(2*222222214. 250P222)(11110所以：公式：根据p元素比较的总次数上界是元素比较的总次数上界是4n19HeJing(2011) School of Software2.3 2.3 堆排序堆排序p堆排序堆排序 把所有要排序的元素构造成一个堆，然后删去根节点上的把所有要排序的元素构造成一个堆，然后删去根节点上的元素

16、。删去最大深度的最右边的叶元素，将其移至根上，元素。删去最大深度的最右边的叶元素，将其移至根上，将这棵树再变成一个堆。以后，重复上述过程，直到这棵将这棵树再变成一个堆。以后，重复上述过程，直到这棵树只剩一个顶点为止。从这个堆的根节点上删去的元素序树只剩一个顶点为止。从这个堆的根节点上删去的元素序列（按删去的先后顺序排列起来）就是一个排序好的非递列（按删去的先后顺序排列起来）就是一个排序好的非递增序列增序列p(最坏情况下时间复杂度为最坏情况下时间复杂度为O(nlog2n)2022-3-22 20HeJing(2011) School of Software2.3 2.3 堆排序堆排序p堆排序的过

17、程是，把初始数据堆排序的过程是，把初始数据“堆化堆化”后，重复执行如下后，重复执行如下两个步骤：两个步骤：1. 删除根节点的元素；删除根节点的元素；2. 将最深最右的叶元将最深最右的叶元素移到根节点并删去这个叶；素移到根节点并删去这个叶；3.重新堆化。重新堆化。p在实际处理时，只需将根节点元素和待删叶元素互换，就在实际处理时，只需将根节点元素和待删叶元素互换，就能达到删除根节点元素和把最深最右的叶元素移至根节点能达到删除根节点元素和把最深最右的叶元素移至根节点上的双重目的，然后对剩下的元素重新堆化。上的双重目的，然后对剩下的元素重新堆化。p例：对例：对50，24，30，20，21，18，3，1

18、2，5，6进进行堆排序。行堆排序。2022-3-22 21HeJing(2011) School of Software2.3 2.3 堆排序堆排序例:对50，24，30，20，21，18，3，12，5，6进行堆排序。下列的图表示删去根元素和重新堆化的过程。50242012530211836(i)624201253021183(ii) 删去删去50，将，将6移至根部移至根部2022-3-22 22HeJing(2011) School of Software2.3 2.3 堆排序堆排序如果用数组记录上述过程，数组元素的变化如下：如果用数组记录上述过程，数组元素的变化如下：(i) 50，24，3

19、0，20，21，18，3，12，5，6(ii) 6， 24，30，20，21，18，3，12，5， 50(iii) 30， 24，6，20，21，18，3，12，5， 50(iv) 30， 24，18，20，21，6，3，12，5， 50302420125621183(iii) 将将6与它的最大儿子与它的最大儿子30交换交换302420125182163(iv) 将将6与它的最大儿子与它的最大儿子18交换交换2022-3-22 23HeJing(2011) School of Software2.3 2.3 堆排序堆排序p算法算法HeapSortp输入：输入：n个元素的数组个元素的数组A1np

20、输出：以非将序排列的数组输出：以非将序排列的数组A1.MakeHeap(A);2.for j n downto 23. 交换交换A1和和Aj;4. Sift_down(A1j-1, 1);5.endfor2022-3-22 不需要额外的临时不需要额外的临时数组，空间复数组，空间复杂性是：杂性是：(1)(1)时间复杂性是：时间复杂性是：O(nlogn)O(nlogn)24HeJing(2011) School of Software2.3 2.3 堆排序堆排序p定理定理 算法算法HEAPSORT对对n个元素排序所需的时间是个元素排序所需的时间是O(nlog2n)。p堆排序的优点是使用空间少，数据

21、结构简单，只需数组堆排序的优点是使用空间少，数据结构简单，只需数组A1:n占用的空间占用的空间p准确来说，准确来说，T(n)=2nlog2n+O(n)2022-3-22 )()log()(122nOiOnTni25HeJing(2011) School of Software2.4 2.4 最大堆与最小堆最大堆与最小堆p最大堆：根节点为最大元素，且二叉树中每一个节点满足最大堆：根节点为最大元素，且二叉树中每一个节点满足堆的性质堆的性质p最小堆：根节点为最小元素，且二叉树中每一个节点满足最小堆：根节点为最小元素，且二叉树中每一个节点满足堆的性质堆的性质p堆是一种相当好的数据结构，具有非常优越的性

22、能。利用堆是一种相当好的数据结构，具有非常优越的性能。利用它，可以实现另一个实用的类它，可以实现另一个实用的类优先队列（优先队列有优先队列（优先队列有着广泛的应用着广泛的应用,在操作系统中在操作系统中,许多消息队列、等待队列等许多消息队列、等待队列等,使用了优先队列，在算法中，我们常用优先队列来实现广使用了优先队列，在算法中，我们常用优先队列来实现广度搜索、贪心算法等）。还可以高效实现哈夫曼编码，可度搜索、贪心算法等）。还可以高效实现哈夫曼编码，可以使以使n2的的Dijkstra算法复杂度降至算法复杂度降至nlogn。2022-3-22 26HeJing(2011) School of Software2.5 2.5 不相交集数据结构不相交集数据结构p假设给定一个有假设给定一个有n个不相同元素的集合个不相同元素的集合S，这些元素被划，这些元素被划分为不相交集合。分为不相交集合。nFind(x)：寻找并返回包含元素：寻找并返回包含