堆和不相交数据结构

堆和不相交数据结构2二叉树性质(Page71)性质1：在二叉树中，第j层的顶点数最多是2j。性质2：令二叉树T顶点数是n，高度是k，那么如果T是完全的，等号成立。如果T是几乎完全的，那么性质3：有n个顶点的完全或几乎完全的二叉树的高度是性质4：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1第2页,共49页，2024年2月25日，星期天性质：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：n1为二叉树T中度为1的结点数因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2

又二叉树中，除根结点外，其余结点都只有一个分支进入设B为分支总数，则n=B+1

又：分支由度为1和度为2的结点射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1第3页,共49页，2024年2月25日，星期天4性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：

(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是

i/2

(2)如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1第4页,共49页，2024年2月25日，星期天54.1引言（堆、不相交集）4.2堆4.2.1堆上的运算4.2.2创建堆4.2.3堆排序4.2.4最大堆和最小堆4.3不相交集数据结构4.3.1按秩合并措施4.3.3Union-Find算法4.3.2路径压缩4.3.4Union-Find算法的分析（略）第5页,共49页，2024年2月25日，星期天64.2堆㈠堆的引入在许多算法中，需要支持下面二种运算： 插入元素 寻找最大值元素（或最小值元素）支持这二种运算的数据结构称为优先队列。可采用下述三种方法实现优先队列：使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。使用排序数组，寻找最大值元素容易，插入操作需移动很多元素。使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。第6页,共49页，2024年2月25日，星期天7定义4.1（Page74）一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设v是一个结点，p(v)是v的父结点，那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。㈡堆的定义（二叉堆）

几乎完全二叉树（Page71）如果一棵二叉树，除了最右边位置上的一个或几个叶子可能缺少外，它是丰满的，我们定义它为几乎完全二叉树。①② ③④ ⑤ ⑥ ⑦⑧⑨⑩几乎完全二叉树例第7页,共49页，2024年2月25日，星期天8堆数据结构支持下列运算DeleteMax(H)：从一个非空堆H中，删除最大键值的数据项，并返回该数据；Insert(H,x)：将数据项x插入堆H中；Delete(H,i)：从堆中删除第i项；MakeHeap(A)：将数组转换为堆。堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。第8页,共49页，2024年2月25日，星期天9㈢堆的表示有n个结点堆T，可以用一个数组H[1..n]用下面方式来表示：T的根结点存储在H[1]中；设T的结点存储在H[j]中，如果它有左子结点，则这个左子结点存储在H[2j]中。如果它还有右子结点，这个右子结点存储在H[2j+1]；若元素H[j]不是根结点，它的父结点存储在H[

j/2

]中。由“几乎完全二叉树”的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。堆具有如下性质：

key(H[

j/2

])≥key(H[j])

2≤j≤n第9页,共49页，2024年2月25日，星期天10201172 93104 115 46 5738 79 510

㈣堆和它的数组表示法把存储在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按1到n”的顺序进行编号，那么数组元素H[i]对应树中编号为i的结点。2017910114537512345678910H[2]=17的左子结点为H[2*2]=H[4]=10H[2]=17的右子结点为H[2*2+1]=H[5]=11H[9]=7的父结点为H[

9/2

]=H[4]=10沿着每条从根到叶子的路径，元素的键值以降序排列。第10页,共49页，2024年2月25日，星期天114.2.1堆上的运算㈠ShiftUp

假定对于某个i＞1，H[i]的键值变成大于它父结点的键值，这样违反了堆的特性，需使用称为ShiftUp的运算来修复堆。

ShiftUp运算沿着从H[i]到根结点的惟一路径，把H[i]移到适合它的位置上。在移动的每一步中，将H[i]的键值与它的父结点H[

i/2

]的键值相比较，若若H[i]＞H[

i/2

]，则H[i]和H[

i/2

]互换（上移），继续。若H[i]≤H[

i/2

]或i＝1，终止。第11页,共49页，2024年2月25日，星期天12②H[5]=25＞H[2]=17，互换。互换后H[5]=17、H[2]=25；①H[10]=25＞H[5]=11，互换。互换后H[10]=11、H[5]=25；H[10]的键值由5变为2520179101145372512345678910③H[2]=25＞H[1]=20，互换。互换后H[2]=20、H[1]=25；25209101745371120179102545371120259101745371120117291041155104537④H[1]=25位于根结点。此时i=1，程序终止。2510第12页,共49页，2024年2月25日，星期天13过程ShiftUp（参见Page75）输入：数组H[1..n]和索引i（1≤i≤n）输出：上移H[i](如果需要)，使它不大于父结点。1. done←false2. ifi＝1thenexit //根结点3. repeat4. ifkey(H[i])＞key(H[

i/2

])then5. 互换H[i]和H[

i/2

]6. else7. done←true8. endif9. i←

i/2

10. until(i=1)ordone第13页,共49页，2024年2月25日，星期天14㈡ShiftDown假定对于某个i≤

n/2

（非叶结点），H[i]的键值变成小于它的左右子结点H[2i]或H[2i+1]的键值，这样违反了堆的特性，需使用称为ShiftDown的运算来修复堆。ShiftDown运算使H[i]下移到二叉树中适合它的位置上。在下移的每一步中，将H[i]的键值与它的子结点键值相比较，若H[i]＜子结点键值，则H[i]与子结点键值中较大者交换（下移），继续；H[i]≥子结点键值或i＞

n/2

，终止。说明：H[i]应与它的子结点中键值较大者交换，被交换者将成为原堆中另一个键值较小的子结点的父结点（如果有的话）。1710 111110 33第14页,共49页，2024年2月25日，星期天15⑵说明：若i＞

n/2

，则该结点位于叶子的位置，无需下移。①② ③④ ⑤ ⑥ ⑦⑧⑨⑩①② ③④ ⑤⑥⑦⑧⑨⑩○

○○○○

n/2=15/2=7

n/2=10/2=5第15页,共49页，2024年2月25日，星期天16H[2]键值由17变为320391011453751234567891020119105453732011910345375②H[5]=3小于H[10]=5，所以H[5]和H[10]互换。交换后H[5]=5，H[10]=3；③H[10]=3位于叶结点位置。i=10>

n/2=5，程序终止。①H[2]=3小于H[4]和H[5]，因为H[4]<H[5]，所以H[2]和H[5]互换。交换后H[2]=11，H[5]=3；201172931041154537532第16页,共49页，2024年2月25日，星期天17过程ShiftDown（Page76）输入：数组H[1..n]和索引i（1≤i≤n）输出：下移H[i]（如果需要），使它不小于子结点。1. done←false2. if2i＞nthenexit //H[i]是叶结点，无需下移。3. repeat4. i←2i

//i指向子结点5. if(i+1≤n)and(key(H[i+1])＞key(H[i]))then6.

i←i+1 //若有右子结点，选择子结点较大者。7. endif8. ifkey(H[

i/2

])<key(H[i])then9. 互换H[i]和H[

i/2

]10. else11. done←true12. endif13. until(2i>n)ordone第17页,共49页，2024年2月25日，星期天18㈢插入为了把元素x插入堆H中，先将堆的大小增1，然后元素x添加到H的末尾，再根据需要将x上移，直到满足堆的特性。若新堆的个数为n，那么堆树的高度为

log2n

所以将一个元素插入大小为n的堆中所需要的时间为O(log2n)算法4.1Insert（77）输入：堆H[1..n]和元素x输出：新堆H[1..n+1]，x为其元素之一。1. n←n+12. H[n]←x3. ShiftUp(H,n)第18页,共49页，2024年2月25日，星期天19㈣删除

要从大小为n的堆中删除元素H[i]，可先用H[n]替换H[i]，然后将堆的大小减1。设原H[i]的键值为key(x)，原H[n]的键值为key(y)， 若key(y)≥key(x)，则执行上移y。

若key(y)＜key(x)，则执行下移y。若i=1，则表示删除堆的最大值。由于堆树的高度为

log2n

，所以删除一个元素所需的时间为O(log2n)。第19页,共49页，2024年2月25日，星期天20算法4.2Delete（Page77）输入：非空堆H[1..n]和索引i（1≤i≤n）输出：删除H[i]的新堆H[1..n-1]1. x←H[i]:y←H[n] //H[i]为要删除的元素2. n←n-13. ifi＝n+1thenexit //删除堆最后一个元素4. H[i]←y5. ifkey(y)≥key(x)then6. ShiftUp(H,i)7. else8. ShiftDown(H,i)9. endif第20页,共49页，2024年2月25日，星期天214.2.2创建堆①方法一给出有n个元素的数组A[1..n]，要创建一个包含这些元素的堆可以这样进行：首先假设堆由1个元素构成，然后将第2个、第3个元素插入堆，直至n个。插入第i个元素，上移次数(循环次数)最多为

log2i

，因此采用这种方法创建堆的时间复杂性为O(nlog2n)。算法MakeHeapByInsert（参见Page77）输入：n个元素的数组A[1..n]输出：堆A[1..n]1. fori＝2ton2. ShiftUp(A,i)3. endfor第21页,共49页，2024年2月25日，星期天224.15给出一个整数数组A[1..n]，可按照下面的方法建立一个A的堆B[1..n]。从空堆开始，反复将A中元素插入B，每一次调整当时的堆，直到B包含A中的所有元素。证明在最坏情况下，算法运行时间是Θ(nlogn)。解：1. fori←1ton2. B[i]←A[i]3. ShiftUp(B,i) //ShiftUp(B[1..i],i)4. endfor在最坏情况下

第22页,共49页，2024年2月25日，星期天234.16用图说明练习4.15的算法对于下面数组的运算。解：

A[1..8]＝69271843B[1..1]=669969629627972697261972618978612978612497861243B[1..8]=B[1..2]=B[1..3]=B[1..4]=B[1..5]=B[1..7]=B[1..6]=第23页,共49页，2024年2月25日，星期天24②方法二设数组A有n=10个元素，构造它的几乎完全二叉树T，如下所示，显然T不是堆。438101113730172612345678910观察数组A的元素：A[

n/2+1]=A[6]，……，A[n]=A[10]，它们对应于T的叶子。这样调整可以从内部结点开始，先调整A[

n/2

]=A[5]，随后调整A[

n/2-1]=A[4]，…，直至A[1]。413283104115136773081792610第24页,共49页，2024年2月25日，星期天2541

32 83

104

115 136 77

308179

2610

438101113730172612345678910A[

n/2

]=A[5]=11A[

n/2

-1]=A[4]=10A[

n/2

-2]=A[3]=8A[

n/2-3]=A[2]=3

A[

n/2-4]=A[1]=443810261373017114383026137101711431330268710171143013326871017114301317268710311304131726871031130261317487103113026131711871034第25页,共49页，2024年2月25日，星期天26算法MakeHeap(Page79)输入：n个元素的数组A[1..n]输出：堆A[1..n]1. fori←

n/2

downto12. ShiftDown(A,i)3. endfor设树T的高度为k=

log2n

，令A[j]为对应于树的第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)第26页,共49页，2024年2月25日，星期天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的高度为k＝

log2n

，令A[j]为对应于树的第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)第27页,共49页，2024年2月25日，星期天28可参考本书Page50（式2.14）第28页,共49页，2024年2月25日，星期天29定理4.1（Page79）使用算法MakeHeap构造一个n元素的堆，令C(n)为执行该算法的元素比较次数，那么n-1≤C(n)＜4n因此构造一个n个元素的堆，算法MakeHeap需要Θ(n)时间和Θ(1)空间。

在过程ShiftDown的每一次循环中，最多有二次元素比较（有二个if语句），因此元素总的比较次数上界为2*2n。同时过程ShiftDown至少执行一次循环，所以元素的最少比较次数由内部结点数决定，元素总的比较次数下界为2

n/2

≥n-1（若原为堆）。第29页,共49页，2024年2月25日，星期天304.2.3堆排序

给定数组A[1..n]，设每个元素的键值是该元素本身，可采用如下方法进行排序：使用算法MakeHeap将数组A变换成堆。首先将A[1]和A[n]交换，显然A[n]为数组中最大元素，然后调用过程ShiftDown将A[1..n-1]转换成堆。接着将A[1]和A[n-1]交换，显然A[n-1]为数组中次最大元素，然后调用过程ShiftDown将A[1..n-2]转换成堆。交换元素和堆调整过程一直重复，直至堆的大小为1。第30页,共49页，2024年2月25日，星期天31算法4.5HeapSort(Page80)输入：n个元素的数组A输出：数组A中元素按升序排列1. MakeHeap(A)2. forj←ndownto23. 互换A[1]和A[j]4. ShiftDown(A[1..j-1],1)5. endfor

这个算法在原有空间进行排序，建立堆用Θ(n)时间，ShiftDown运算用O(log2n)时间，并且重复n-1次。参考习题4.14第31页,共49页，2024年2月25日，星期天32

这个算法在原有空间进行排序，建立堆用Θ(n)时间，ShiftDown运算用O(log2n)时间，并且重复n-1次，显然建立堆所用的时间为低次项，可略。定理4.2(Page80)算法HeapSort对n个元素排序，需要用O(nlog2n)时间和Θ(1)空间。由此可见，堆排序是最优秀的排序算法。4.2.4最大堆和最小堆最大堆：最大键值元素存放在根结点。最小堆：最小键值元素存放在根结点。第32页,共49页，2024年2月25日，星期天334.3不相交集数据结构（并查集）是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。如数据结构课中讲到的最小生成树Kruskal算法：Kruskal是一种贪心算法，比较适用于稀疏图:为使生成树上边的权值和最小，则应使生成树中每一条边的权值尽可能地小。具体做法:找出森林中连接任意两棵树的所有边中，具有最小权值的边，如果将它加入生成树中不产生回路，则它就是生成树中的一条边。这里的关键就是如何判断"将它加入生成树中不产生回路"。第33页,共49页，2024年2月25日，星期天344.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},{4,8},{9}4个子集依次被命名为1、3、8、9。第34页,共49页，2024年2月25日，星期天35我们对Union和Find二种不相集运算定义如下：Find(x)：寻找并返回包含元素x的集合名字。Union(x,y)：将包含元素x和y的二个集合用它们的并集替换。并集的名字，或为包含元素x的那个集合的名字，或为包含元素y的那个集合的名字。我们目的是设计这二种运算的有效算法，为此需要一种数据结构，它既要简单，又要能有效实现合并和寻找这二种运算。第35页,共49页，2024年2月25日，星期天36㈡不相交集数据结构①将用于命名子集名称的元素视为根，其余元素视为其后代，每个子集可用一棵根树来表示，这样便形成了森林。9②每个结点都有一个指针。非根结点的指针指向它的父结点；根结点的指针值为0，表示不指向任何结点。③根结点用作集合的名字。④森林可方便地用数组A[1..n]。A[j]是j的父结点，若A[j]=0，说明j是根结点。⑤对于任一元素x，用root(x)表示包含x的树的根，例root(6)=3。030822100111234567891011841710113256第36页,共49页，2024年2月25日，星期天37㈢不相交集运算实现①Find(x)寻找并返回包含元素x的树的根。例， Find(6)=root(6)=3②Union(x,y)

将包含x和y的二个不相交集合并成一个集合，也就是说把二棵树合并成一棵树，Union(x,y)可表示为Union(root(x),root(y))。若合并后树的根为root(x)，则有A[root(y)]=root(x)。若合并后树的根为root(y)，则有A[root(x)]=root(y)。84984 9或984例，Union(4,9)=Union(root(4),root(9))=Union(8,9)80012345678910118第37页,共49页，2024年2月25日，星期天384.3.1按秩合并措施nn-1……21㈠问题的提出若直接进行合并运算有个明显缺点，在极端情况下，树有可能退化成线性表。假定从单元素集合{1},{2},…,{n}开始，执行下面的合并序列（假设第二个参数为合并后树的根）： Union(1,2),Union(2,3),…,Union(n-1,n)形成的树如左图所示。执行下面的寻找序列： Find(1),Find(2),…,Find(n)n次寻找运算总的代价为：第38页,共49页，2024年2月25日，星期天39㈡引入秩

为了限制每棵树的高度，采用秩合并的措施。给每个结点存储一个非负数作为该结点的秩（记为rank），初始时每个结点的秩均为0。设x和y是二棵不同树的根，执行Union(x,y)时，比较rank(x)和rank(y)，若rank(x)<rank(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)不变。第39页,共49页，2024年2月25日，星期天40x1100y2215060y1100x221506071100y2215060x2rank(x)<rank(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第40页,共49页，2024年2月25日，星期天41令x是任意结点，p(x)是x的父结点，有下面二个基本观察结论。观察结论4.1(Page82)rank(p(x))＞rank(x)观察结论4.2(Page82)rank(x)的值初始化为0，在后继合并运算序列中递增，直到x不是根结点。一旦x变成了其它树的子结点，它的秩就不再改变。第41页,共49页，2024年2月25日，星期天424.3.3Union-Find算法算法4.6Find（参见Page83)输入：结点x输出：root(x) ，包含x的树的根。0.procedureFind(x)1. y←x2. whilep(y)≠0 //p(y)=0表示y是根结点3. y←p(y)4. endwhile5. root←y6. returnroot7.endprocedure //注：路径压缩被略去第42页,共49页，2024年2月25日，星期天43算法4.7Union(Page83)输入：结点x和y输出：包含x和y的二棵树的合并0.procedureUnion(x,y)1. u←Find(x):v←Find(y)2. ifrank(u)≤rank(v)then3. p(u)←v//包含y的树的根结点v是合并后的根结点4. ifrank(u)=rank(v)then5. rank(v)=rank(v)+16. endif7. else//rank(u)>rank(v)8. p(v)←u//包含x的树的根结点u是合并后的根结点9. endif10