《第4章 堆和不相交数据结构》由会员分享，可在线阅读，更多相关《第4章 堆和不相交数据结构（44页珍藏版）》请在金锄头文库上搜索。
1、1,第4章 堆和不相交集数据结构,上海第二工业大学 温敬和 2008年4月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
3、中，删除最大键值的数据项，并返回该数据； InsertH,x：将数据项x插入堆H中； DeleteH,i：从堆中删除第i项； MakeHeapA：将数组转换为堆。,堆的蕴含特性： 沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。,6,堆的表示 有n个结点堆T，可以用一个数组H1.n用下面方式来表示： T的根结点存储在H1中； 设T的结点存储在Hj中，如果它有左子结点，则这个左子结点存储在H2j中；如果它还有右子结点，这个右子结点存储在H2j+1； 若元素Hj不是根结点，它的父结点存储在Hj/2中。 由 “几乎完全二叉树” 的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点
4、。 堆具有如下性质： key(Hj/2)key(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的键值变成大于它父结点
5、的键值，这样违反了堆的特性，需使用称为ShiftUp的运算来修复堆。 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
6、。,10,过程 ShiftUp（参见Page 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的键值变成小于它的左右子结
7、点H2i或H2i+1 的键值，这样违反了堆的特性，需使用称为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 17
8、239 1011545 37510,H2=3和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
9、)key(Hi) then 6. ii+1 /若有右子结点，选择子结点较大者。 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,
10、删除 要从大小为n的堆中删除元素Hi，可先用Hn替换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.
11、if key(y)key(x) then 6.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 fo
12、r,19,方法二 设数组A有n=10个元素，构造它的几乎完全二叉树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
13、An/2-3=A2=3 An/2-4=A1=4,几乎完全二叉树的变化详见黑板,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层结点
14、下移最多次数20(k-0),令k=log2n，设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
15、),23,可参考本书 Page 50（式2.14）,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，设每个元素的键值是该元素本身，可采用如下方法进行排序： 使用算法MakeHeap将数组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
