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

《高级数据结构对算法的优化..》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、359127高级数据结构对算法的优化南京外国语学校黄炎邮编：210042[摘要]使用高级数据结构对算法进行优化的效果有目共睹。本文针对两种基于二杈树的高级数据结构：堆和排序二杈树展开讨论，说明了两种数据结构的特点、优势和使用方法，并附有实例和数据对比。[关键字]数据结构算法优化堆排序二杈树堆是一棵完全二杈树，它满足这样的条件：对于每一个非叶节点，它的值都大于它的两个子节点的值（最大堆）或小于它的两个子节点的值（最小堆）。山于堆是-•棵完全二杈树,所以我们一般采用数组的方法存储堆。如下定义：Heap:Array[l..n]ofNode;那么，一个最

2、人堆一定满足：Heap[i]Heap[iDiv2]ie（2,n）0不难发现，一个堆的根节点（第一个元素）一定是这个堆中最大的（最大堆中）或是最小的（最小堆中）。这正是堆这种数据结构的价值所在，牢牢抓住这一点，就可以使堆发挥岀其最大功效。首先，我们讨论堆的构造。对于一串无序数列&

3、用2・・・％,我们将克存入数组中，这样,这一串数实际上已经对应了一个完全二杈树。以3,5,9,127为例:我们可以把数组看作是顺序编号的一棵完全二杈树（如图1）。对于这样一棵完全二杈树，要对其进行

4、修改，使其最终形成堆。假定要生成一个最人堆，那么根据最大堆的定义，在这个完全二杈树中，没冇哪个非叶节点的值要比其子节点还小。所以，要使右边这棵二杈树也满足这样的条件，就需要対节点按照从后向前的顺序进行“筛”运算。只不过这里的“筛”不是把节点筛下去，而是把某些节点“筛上去”。从后往前，第一个节点是⑦，但是其父节点⑨的值较大，所以不需要“筛”它。一直搜到节点⑨，我们发现其值要比其父节点③大，所以要把它向上“筛”。我们把⑨和③换个位置，让较大的⑨做父节点，较小的③做子节点。但这还没完，我们发现经过修改后，先前提到的⑦的值比其现在的父节点③的值要大了，所

5、以，我们述要把⑦向上“筛”。于是③又和⑦换了一个位置，变成了⑦的子节点。事实上，为了保证算法的正确性，在每次“筛”的时候，都要“一筛到底”，时刻注意被“筛”卜•來的节点是否还要继续往卜•“筛”。注意：如果一个待“筛”的节点的值同时比其两个了节点都要小，就应该用较大的了节点与其对换位置。经过“筛”运算，可以得到这样一个堆：见图2。它满足最人堆的性质：对于每一个非叶节点,它的值都人于它的两个子节点的值。同时注意：根节点⑨的值是所有元素屮最人的。下面给出构造堆的源程序：Fori:=nDownTo2Do｛从最后一个节点开始从后往前进行"筛”运算｝IfH[

6、i]>H[iDiv2]Then｛若此节点的值比其父节点的值要大｝Begint:=H[i];H[i]:=H[iDiv2J;H[iDiv2]:=t;｛交换此节点与其父节点｝j：=2*i;｛先将指针指向其左子节点｝Whilej<=nDo｛下标不越界｝BeginIf(j+l<=n)and(H[j]

7、j+lJ)ThenInc(j);｛若此节点冇右子节点并H.右子节点的值比左子节点的值要大，则将指针指向具右子节点｝IfH[i]

8、j]:=t;｛交换此节点于其

9、子节点｝i:=j;j:=2*i｛重新定位指针，准备下-•次循环｝EndElseBreak｛若不需要再“筛”就退出｝EndEnd;上述算法中“筛”运算的时间复杂度约为Ogg?N),是相当高效的。注意到根节点的值是所有节点的值中最大的，抓住这一点，就不难设计出一套时间复朵度约为O(Nlog2N)的算法：把数组分成两个部分，一个部分为已排序区间，在这里的元素都是有序的。另一部分为堆区间，把这里的所有元素理解为一个堆。一开始，已排序区间为空，堆区间为全体元素。首先构造一个堆，把堆的根节点移入己排序区间，然后对剩卜•來的堆再进行“筛”运算,再次得到一个堆之

10、后，再把堆的根节点移入已排序区间，如此往复直到己排序区间为全体元索，堆区间为空，则排序过程结束。这时，已排序区间中的元索就都是冇序的了。这种O(Nlog2N)的算法其实就是所谓的堆排序。(源程序见附录,有关堆排序的效率以及特点参看卜面有关排序二杈树的内容)堆在实际解题吋有着很重要的应用，使用得好往往能够收到出乎意料的效果。下而用一道例题来说明堆在解题中的应用。例1：黑匣子我们使用黑匣子的一个简单朕型。它能存放一个整教序列和一个特别的变量i。在初始肘刻，黒匣子为空且i等于0。这个黑匣子能执行一糸列的命令。有两类命令：ADD(x)：把元素x放入黒匣子

11、；GET：把i加1的同肘，输出黒匣子内所有整数中第i小的数。半记第i小的数是当黑匣子中的元素己非降序排序后伐于第i住的元素。编号命令•黑