高级数据结构对算法的优化

南京外国语学校黄炎第1页共23页高级数据结构对算法的优化南京外国语学校黄炎邮编：210042[摘要]使用高级数据结构对算法进行优化的效果有目共睹。本文针对两种基于二杈树的高级数据结构：堆和排序二杈树展开讨论，说明了两种数据结构的特点、优势和使用方法，并附有实例和数据对比。[关键字]数据结构算法优化堆排序二杈树一、堆堆是一棵完全二杈树，它满足这样的条件：对于每一个非叶节点，它的值都大于它的两个子节点的值（最大堆）或小于它的两个子节点的值（最小堆）。由于堆是一棵完全二杈树，所以我们一般采用数组的方法存储堆。如下定义：Heap:Array[1..n]ofNode;那么，一个最大堆一定满足：n)(2,i2]Divi[Heap]i[Heap；同样，对于最小堆有：n)(2,i2]Divi[Heap]i[Heap。不难发现，一个堆的根节点（第一个元素）一定是这个堆中最大的（最大堆中）或是最小的（最小堆中）。这正是堆这种数据结构的价值所在，牢牢抓住这一点，就可以使堆发挥出其最大功效。首先，我们讨论堆的构造。对于一串无序数列n21aa,a，我们将其存入数组中，这样，这一串数实际上已经对应了一个完全二杈树。以3,5,9,1,2,7为例：我们可以把数组看作是顺序编号的一棵完全二杈树（如图1）。对于这样一棵完全二杈树，要对其进行修改，使其最终形成堆。假定要生成一个最大堆，那么根据最大堆的定义，在这个完全二杈树中，没有哪个非叶节点的值要比其子节点还小。所以，要使右边这棵二杈树也满足这样的条件，就需要对节点按照从后向前的顺序进行“筛”运算。只不过这里的“筛”不是把节点筛下去，而是把某些节点“筛上去”。从后往前，第一个节点是○7，但是其父节点○9的值较大，所以不需要“筛”它。一直搜到节点○9，我们发现其值要比其父节点○3大，所以要把它向上“筛”。我们把○9和○3换个位置，让较大的○9做父节点，较小的○3做子节点。但这还没完，我们发现经过修改后，先前提到的○7的值比其现在的父节点○3的值要大了，所以，我们还要把○7向上“筛”。于是○3又和○7换了一个位置，变成了○7的子节点。事实上，为了保证算法的正确性，在每次“筛”的时候，都要“一筛到底”，时刻注意被“筛”下来的节点是否还要继续往下“筛”。注意：如果一个南京外国语学校黄炎第2页共23页待“筛”的节点的值同时比其两个子节点都要小，就应该用较大的子节点与其对换位置。经过“筛”运算，可以得到这样一个堆：见图2。它满足最大堆的性质：对于每一个非叶节点，它的值都大于它的两个子节点的值。同时注意：根节点○9的值是所有元素中最大的。下面给出构造堆的源程序：Fori:=nDownTo2Do{从最后一个节点开始从后往前进行“筛”运算}IfH[i]H[iDiv2]Then{若此节点的值比其父节点的值要大}Begint:=H[i];H[i]:=H[iDiv2];H[iDiv2]:=t;{交换此节点与其父节点}j:=2*i;{先将指针指向其左子节点}Whilej=nDo{下标不越界}BeginIf(j+1=n)and(H[j]H[j+1])ThenInc(j);{若此节点有右子节点并且右子节点的值比左子节点的值要大，则将指针指向其右子节点}IfH[i]H[j]Then{若仍需要再往下“筛”，则}Begint:=H[i];H[i]:=H[j];H[j]:=t;{交换此节点于其子节点}i:=j;j:=2*i{重新定位指针，准备下一次循环}EndElseBreak{若不需要再“筛”就退出}EndEnd;上述算法中“筛”运算的时间复杂度约为)N(logO2，是相当高效的。注意到根节点的值是所有节点的值中最大的，抓住这一点，就不难设计出一套时间复杂度约为)NlogN(O2的算法：把数组分成两个部分，一个部分为已排序区间，在这里的元素都是有序的。另一部分为堆区间，把这里的所有元素理解为一个堆。一开始，已排序区间为空，堆区间为全体元素。首先构造一个堆，把堆的根节点移入已排序区间，然后对剩下来的堆再进行“筛”运算，再次得到一个堆之后，再把堆的根节点移入已排序区间，如此往复直到已排序区间为全体元素，堆区间为空，则排序过程结束。这时，已排序区间中的元素就都是有序的了。这种)NlogN(O2的算法其实就是所谓的堆排序。（源程序见附录，有关堆排序的效率以及特点参看下面有关排序二杈树的内容）堆在实际解题时有着很重要的应用，使用得好往往能够收到出乎意料的效果。下面用一道例题来说明堆在解题中的应用。例1：黑匣子我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令：ADD(x)：把元素x放入黑匣子；GET：把i加1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。南京外国语学校黄炎第3页共23页下面是一个11个命令的例子：编号命令i黑匣子内容输出1ADD(3)032GET1333ADD(1)11,34GET21,335ADD(-4)2-4,1,36ADD(2)2-4,1,2,37ADD(8)2-4,1,2,3,88ADD(-1000)2-1000,-4,1,2,3,89GET3-1000,-4,1,2,3,8110GET4-1000,-4,1,2,3,8211ADD(2)4-1000,-4,1,2,2,3,8现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多个有30000个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面得两个整数序列描述命令序列：1．A(1),A(2),……,A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。2．u(1),u(2),……,u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1,2,6,6)。你可以假定自然数序列u(1),u(2),……,u(N)以非降序排列，N≤M，且对于每一个p（1≤p≤N）有p≤u(p)≤M。输入M,N,A(1),A(2),……,A(M),u(1),u(2),……,u(N)，输出黑匣子的处理结果。解：显然，此题实际上已经给出了程序基本的算法流程如下：ProcedureBlackBox(M,N,A,u);Begini:=1;Forj:=1ToMDoBeginAdd(A[j]);While(i=N)and(u[i]=j)DoBeginGet(i);Inc(i)EndEndEnd;当然，此题远没有这么简单。上面程序中的两个过程：Add和Get是要我们自己去编写的，而且，这两个过程的效率直接决定了整个程序的效率。如果这两个过程都能够应付上限为30000的测试数据，那么整个算法就是成功的。事情往往没有这么简单，凭直觉我们就能够发现，上述两个过程的关键在于数据结构的选择。我们先采用朴素的，也是最常用的线性表来解题：最基本的想法是不考虑黑匣子内数的有序性，每执行一次Get命令就把黑匣子内南京外国语学校黄炎第4页共23页的数全部排一个序。这种算法实在是太朴素了，不难得出其Add过程的时间复杂度为O(1)，而Get过程的时间复杂度为O(mlog2m)。这样，整个程序的时间复杂度就为O(M+MNlog2M)！我们认为这是一个O(n2log2n)的算法，在n的上限为30000时是绝对不可采用的！显然，上面的算法过于朴素了，我们完全可以时刻保持黑匣子内数的有序性，这样，Get命令的时间复杂度就被降到了O(1)。但是，在执行Add命令时，我们需要使黑匣子内的数保持有序，这就需要一个插入排序的过程。这样，Add命令的时间复杂度就应为O(m)。那么，整个程序的时间复杂度为O(m+mn)，我们认为这是一个O(n2)的算法。（源程序见附录。）虽然程序的速度有所提高，但是对于令人恐怖的上限为30000的数据，这样的程序的效率依然不令人满意，对于极限数据，一般需要约11秒才能出解，这仍然是不能接受的。因此，我们可以换一种数据结构，采用堆来存储黑匣子内的数并进行运算。堆的重要性质在于堆的根节点的值是堆中全部节点的值中最大（最大堆）或最小（最小堆）的。由此，如果使得堆的根节点就是整个黑匣子中第i大的数，那么程序的效率将提高很多。这里有一个很巧的方法：构造两个堆：一个最大堆，一个最小堆，把黑匣子中的数排序，前i个数放入最大堆中，之后的数放入最小堆中（没有就不放），这样最大堆的根节点的值就总是黑匣子中第i大的数。接下来我们所要做的就是保证在执行Add和Get命令之后，两个堆依然保持原有性质。这样，Add过程实际上是一个往堆中插入元素的过程，其时间复杂度为O(log2M)；Get过程需要调整两个堆的大小（i发生了变化），也需要进行堆的插入过程，其时间复杂度为O(log2N)。那么，整个程序的时间复杂度为O(Mlog2M+Nlog2N)，我们认为这是一个O(nlog2n)的算法，其效率是相当令人满意的，对于极限数据，都可以在0.1秒左右出解。下面给出使用上面有关堆的算法中Add和Get过程的两个过程的源程序（整个程序参见附录）。ProcedureAdd(num,i:LongInt);Varj,k,t:LongInt;BeginIftop1iThen{如果最大堆中的数少于i个}BeginInsert1(num);{向最大堆中添加数据num}Exit{退出}End;Ifnum=b1[1]ThenInsert2(num){如果待添加数据大于第i大的数（最大堆的根节点b1[1]）则将其插入至之后的最小堆中，否则将其插入最大堆中}ElseBeginInsert2(b1[1]);{把最大堆中最大的数（根节点）插入最小堆中}b1[1]:=num;{把最大堆的根节点替换为待添加数据，并进行维持最大堆性质的“筛”运算}j:=1;k:=2;Whilek=top1DoBeginIf(ktop1)and(b1[k]b1[k+1])ThenInc(k);南京外国语学校黄炎第5页共23页Ifb1[j]b1[k]ThenBegint:=b1[j];b1[j]:=b1[k];b1[k]:=t;j:=k;k:=j*2EndElseBreakEndEndEnd;ProcedureGet;Varj,k,t:LongInt;BeginWriteln(f,b1[1]);{输出第i大的数（最大堆的根节点b1[1]）}Iftop20Then{如果最小堆不为空，则}BeginInsert1(b2[1]);{把最小堆中最小的数（最小堆的根节点b2[1]）插入最大堆中}b2[1]:=b2[top2];{从最小堆中删除根节点}Dec(top2);j:=1;k:=2;Whilek=top2DoBeginIf(ktop2)and(b2[k]b2[k+1])ThenInc(k);Ifb2[j]b2[k]ThenBegint:=b2[j];b2[j]:=b2[k];b2[k]:=t;j:=k;k:=j*2EndElseBreakEndEndEnd;下面给出一个表格，比较在不同数据量下程序BlackBox1（采用线性表）和BlackBox2（采用堆）的耗时。（测试机型为PIII800，128MSD）表1数据量（N）BlackBox1的耗时(s)BlackBox2的耗时(s)110000.000.00220000.050.00350000.330.004100001.210.055200005.050.0563000011.320.11不难发现，采用堆的BlackBox2在时间复杂度上要明显优于采用线性表的BlackBox1，足见堆的优越性。南京外国语学校黄炎第6页共23页二、排序二杈树同堆一样，排序二杈树也是一种拥有特定性质的二杈树。其定义为：排序此二杈树是一颗空树或具有下列性质的树：(1)若其左子树非空，则左子树上锁有节点的值均小于根节点的值。(2)若其右