大家好，数据结构与算法这一 Hello everyone , for this lecture of data structure and algorithm
讲，我们继续第九章，外排序的学习。今天我们学习外排序的相关算法。 we continue Chapter IX, external sort. Today we related algorithms of external sort.
外排序是对磁盘文件进行的排序操作。 External sort is a sorting operation for files on the disk.
它主要分为两个步骤。首先，就是形成 It is mainly divided into two steps. First is the formation of
尽可能长的初始的排序顺串。 the initial sorting string as long as possible.
另外，我们对这些顺串最后进行一些处理， In addition, we deal with these strings at last.
把它整理成整个排序的文件。 It is organized into the entire sorting files.
那我们来看形成初始顺串的一个有效的算法。这是一个 Then we see an efficient algorithm that forms the initial string. This is a process of
置换选择排序。那我们用到这样的一个内部的堆。 replacement selection sort. Then we use such an internal heap.
然后我们不断地从输入缓冲区里面输出数据到 Then we continue to the output data from the input buffer to heap.
堆。然后，经过堆的这些处理，我们得到 Then, after the treatment of the heap, we get
输出缓冲区里面的一个有序的这样一个序列的结果。 the results of such an ordered sequence in the output buffer.
这个结果我们把它输出到磁盘里面，就形成了初始的排序顺串。 This result is exported to the disk, on the formation of the initial sorting string.
我们来看，置换选择排序, Then let us look at the process of replacement selection sort.
它的处理的一个过程。首先， First of all,
它形成了这么一个初始的堆。这些， It forms such an initial heap. In these heaps,
它元素本身也是从我们待排的那个整体的大文件里面， the element itself is the data
获得的这些数据。 from our whole large files that need to be sorted.
然后我们这个堆顶，它是可以出到 Then the top of the heap is possible
我们这样的一个输出的结果里面。 to be output to such a result of our output.
这个输入的数据里面，这些值，它 this input data,these values,
是不是能够输出到顺串，是不是能够进入我们的堆？ Is it able to be output to the string and enter into our heap?
那需要跟这个堆顶进行比较。如果这个堆顶呢， That needs to be compared with the top of the heap. If the top of the heap,
比我们输入的这个数值要小， is, smaller than this input value,
那这个数值，可以进入到堆，我们进行后面的这个处理。 this value can enter into the heap, we,continue the process afterwards.
那进到堆里面，我们显然是要对这个堆，进行一个重新的调整。 If it enter into the heap, we obviously need to do a new adjustment on this heap.
那如果这个值比堆顶要小，那它就不能够进到我们这个堆里面。 So, if this value is smaller than the top of the heap, it will not be able to enter into our heap.
这个堆我们把它缩小规模1。我们 the size of the heap will be reduced by 1.
把这个堆底下的那个元素换上去，作为这个堆顶， then we will replace with the element at the end of the heap,as the top of the heap,
而且重新调整堆。不合法的这个值，我们还是搁在这个存储单元里面。我们等 And re-adjust the heap. Then,this value is not legitimate, and that we put it in the storage unit. We waited
待下一次，见下一个顺串的时候，我们可以用这个值。 until next time for another string, we can use this value.
我们一直这样处理，我们这个堆的规模越来越小， We continue this treatment like this, then the heap size will be smaller and smaller,
然后，我们这个输出的这个顺串，它当然是越来越大。 And then, the output of our string along is certainly growing bigger and bigger.
然后，不能够进入刚才这个堆的这些数据，它慢慢地 And then, those not able to enter the that heap is slowly and slowly
就充满了这个被缩小的这个堆的这些空间。然后我们 getting full of these spaces that is reduced from the heap. Then
在这个规模缩为0，也就是这个堆里面没有东西了以后， when this scale is reduced until0, there is nothing in this heap,
它又用这些刚才存在这里的这些值，再重新建堆， these values saved here are used to rebuilt the heap.
然后我们再从这个待处理的输入文件里面，去找数据，然后再去形成 We then from the input files to be processed find data, and then form
另外一个这样的已排序的顺串。 another such sorted string.
我们再来看一下， Let us take a look
置换选择排序它的算法。那这些部分， at the replacement selection sort algorithm. These parts
就是这个算法的相关的一些参数的定义。 is to define the parameters related to this algorithm.
我们来看算法的核心的过程。 Well, let's look at the process of the core of the algorithm.
我们是对这个堆进行操作， Well, we will do the operation on the heap,
一直到这个堆的规模还没有缩小为0的时候， Well, until this has not reduced the size of the heap to zero,
我们首先从这个堆顶，去找到它相应的一个根的这个元素。然后把这个元素输出到这个顺串里面。 Then we, first find from the top of the heap. the root element. Then this element is output to this string.
接着呢，我们从输入缓冲区里面读一个记录，跟这个堆顶进行比较。 Then, we read a record from the input buffer, compared with the top of the heap.
如果它比堆顶要大，那我们可以把它就放到这个空的堆顶。 If it is larger than the top of the heap , then we can put it into the empty top of the heap .
如果它比堆顶要小，我们先把这个堆的最后的那个元素给它转到堆顶。然后，我们把这个新的，这个较小的元素， Ah, if it is smaller than the top of the heap, we put this last element of the heap to the top of the heap. And then, we put this new and smaller element,
给它放到我们腾出来的那个最后的位置，而堆的规模要减1。 to the final vacated position, and the size of the heap minus 1.
然后，这两种情况下，我们都是要对这个堆 Ah then , in both cases , we are going to readjust the heap.
进行一个重新的调整工作，都是从根开始的。那我们一直重复 they both start from the root. Then we have to repeat
这个过程 ，那直到这个堆的规模，是变成了0。 this process until the size of turned into 0.
然后我们形成了一个已经排序的这么一个顺串。 Then we form such a sorted string.
然后我们，就把那个数组里面拥有的那些哦，那些乱七八糟的这个元素， Then we use those elements in the array with a mess,
我又重新建堆，然后再继续从待处理的这个排序文件里面， to rebuilt the heap, and then continue from this sort files to be processed,
来找新的元素来进行，形成顺串的这样的工作。 to find new elements to form string.
我们看这样的一个置换选择排序，它能形成多大规模的顺串呢？ Then let us look at such a replacement selection sort. How large scale it can form a string?
如果你这个堆的规模你是能够容纳M个记录，那 If the size of the heap is able to accommodate M records,
最小的情况下，我们这个顺串长度，起码是这M个记录。就是你这个原来 under the condition of minimum, the length of the string, at least, is M records. This is your original
最开始形成那个堆。最好的情况下如果你输入就是一个有序的序列， heap from start. Well, the best case is that if you enter an ordered sequence,
我们可以整个经过一轮处理，就变成整个有序的这个状态。 we can make it in order through the whole round of treatment.
平均情况下呢，我们是能够形成长度为2M的顺串。 In average case, we are able to form a string with the length of 2M.
我们看，这么一个扫雪机的模型。 Let us see such a snowplow model.
假设这是一个操场，形成一个圆圈。 Assuming this is a playground, forming a circle.
然后，现在，雪已经下满这个操场， And then, the snow has filled the playground,
而且正在均匀地下着，那在 And it is still snowing evenly.
经过了这几轮的这个清扫，达到一个稳定状态以后呢， After several rounds of cleaning, after it reaches a steady state ,
我们可以看到，每一轮，这样的清扫，它 We can see the amount of snow for each time
所得到的这个雪的量，就是我刚才 存在这个操场上的这些雪的容量的两倍。 is twice the capacity of the snow on the playground.
因为我们再往前头看的时候，这个是一个满的。 because when we see it ahead, this is a full.
然后我这个后面正好是空的，我一直这么走过来， Then my back is just empty, and I go along in this way,
每扫一圈，都是扫到两倍的雪量。 Each sweep circle is sweeping twice the amount of snow. Well,
已经形成了这么若干个初始顺串以后， After forming such a number of initial strings,
我们怎么样最终形成一个已排序的文件呢？很显然可以用归并的方法。 how we eventually form an ordered file? it is clear that the merge method can be used.
因为这些原始的顺串，它的长短是不一定的， Because the length of the original string is unknown,
因此我们在归并的这个过程中，其实是 in the merge process, in fact,
应该用Huffman 树来规划它的这个归并顺序。 Huffman tree should be used.
我们来看一下这个二路归并的例子。 Then let us look at this example of two-way merge sort.
我们如果是这些原始顺串，是这6个，然后每一个，它的 If the original strings is such six, and every one
这个长度都是由3个磁盘块组成。 is made up of the three disk blocks.
每一个磁盘块里面呢有250个记录，我们这样的两两归并去进行。 Each disk block have 250 records, so if we do the pairwise merge,
我们可以看到，它所需要的这么一个 as we can see,
磁盘的访外次数，就是读和写，各有48次。 the number of visits outside on the disk of read and write is each 48 times.
我们如果要提高它的这样的一个归并效率， If you want to improve its efficiency,
我们可能需要采用多路归并，例如这就是一个3路归并的例子。 we may need to use multi-way merge algorithm, such as this three-way merge example.
在多路归并的情况下，我们每一次从这几个顺串里面找最小。 In the case of multi-way merge, and each time we find the minimum form those strings.
如果我是逐个去看，这是一个比较低效的方法。 What if I see it one by one? This is a relatively inefficient way .
而且如果k比较大的时候，我们是不是能够复用前面已经看过的这个结果呢？ And if k is relatively large, are we able to, reuse the result before?
我们的方法就是采用一种叫做选择树的这样一个结构。 Our approach is to use such a structure called a selection tree.
我们可以达到一个更高效的一个操作的结果。 A result that we can achieve is more efficient.
我们看一下这个赢者树。 Then let us look at this winner tree.
这个赢者树，我们是这么来组织的。 We organize the winner tree in this way.
这些方框就是我们待处理的这个顺串。 In these boxes are strings to be processed.
其实我们是把这个顺串， Actually we
读取了若干个这样的它的前面的几框。然后 read a plurality of such elements in the front of these strings. Then
放到这个磁盘的缓冲区，放到内存的这个缓冲区里面。 put them into the disk buffer and into this memory buffer.
为了组织这个比赛呢我们形成这样一个完全二叉树。 in order to organize this competition, we form such a complete binary tree.
这些圆圈的内部节点呢，它就是索引的我们在这些， The internal nodes of these circles are the index of those,
外部结点它的比赛结果的那个赢者的那个顺串的索引下标。 that win the game.
我们有这么几个参数。 We have such few parameters.
根据我们这个外部结点， According to our external nodes,
它是在最外层还是在倒数第二层， it is in the outermost layer or in the penultimate,
我们可以得到它相应的这个父结点的下标位置。 We can get the corresponding subscript position of the parent node.
我们来看一下，这个赢者树 Then let us look at this, winner tree , ah.
很明显就是，从这个左到右，来 It is clear that the external node number
安排这个外部结点的编号的。 is arranged, from left to right.
然后，内部结点呢，我们还是按照，完全二叉树从上到下，从左到右来编号的。 Then, the internal nodes still follow, the complete binary tree from top to bottom , left to right.
那我们把所有的这些两两比赛 That we , make all these pair games.
的结果的赢者，把它放在这个当前这个结点。 The winner is put in the current node.
我再来看它的一个重构的这个过程。 Well, let us look at this reconstruction process.
假设我们当前的这样的一个全局最优的是这个，顺串4，然后，它的值是6。 Suppose the present global optimum is in the string 4 with its value 6.
这个6，它出列以后呢，我们后面，它的这个次小又要顶上来。 6, after it is out of the line, the second smallest should move up.
那15顶上来以后呢，它继续进行比赛。 After the 15 come up, it continues to play the game.
我们就是，要跟它的相应的这个兄弟结点进行比赛。 It should play with its brother node.
然后，我们再选出这个全局的最优。这一次， And then, we'll elect another global optimum. Well, this time,
就是，这个顺串5，呃，所在的这个 顺串，然后它的值是8。 That is ,this string 5 , then its value is 8.
这里边我们看到，在比赛的时候我还要去看这个，兄弟的结点。 Here we see that in the game I have to see the brother node.
这个就不是特别方便，因此我们有一种修改的方法呢，就是败方树。 This is not particularly convenient, so we have a modified approach, that is, the loser tree.
这个败方树，它的特点就是，我每次呢，把这个， The loser tree, its characteristic is that every time I put the
失败的，这个顺串的索引， 放在当前这个父结点的这个位置。 loser in the position of the parent of the current node.
而胜者，我们其实是往上面去传递了。 And for the winner, we actually pass on up.
其他的这些参数是跟赢者树是一样的。 The other parameters are the same as the winner tree.
那我们来看 Then let us look at,
有一个，这个特殊的情况，就是外部结点， there is one particular case, that is, the number of external nodes.
个数，它如果是奇数的情况下，我们会有一次内部节点和外部结点的比较。 If it is odd, we will do a comparison between internal nodes and external nodes.
在这个时候，我们处理这些结点时候要做一下特殊的处理。 At this time, we do some special handling when dealing with these nodes.
我们再来看，对于这样的一个败方树， For such a loser tree,
当我们选出全局的最优者的时候，然后我，下面， when we have elected the global optimum and then I
把它出列，然后次优顶上来的时候，我们比赛，只需要 put it out of the line, and then suboptimal come onto the top. The match is only needed with
去跟父结点，就是说，是上次比赛的那个，失败的那一方， its parent node, that is to say, is, the failure of last game,
去比，就传到根，比刚才的赢者树，要更便捷一些。 Until reaching the root. It is more convenient than the winner tree just now.
我们看一下，败方树的ADT。那现在是， Then let us look at the ADT of loser tree. That is
一些这个参数的定义，那我们，重要的是这么一个Play的函数。 some definition of these parameters. Then what is important is such a Play function.
还有后面这个，我们建立这样的一个败方树的一个初始化的 and the initialization after establishing such a loser tree.
工作。还有，在一个全局最优，出列以后， Also, after the global optimum get out of line,
我们来重置这个败方树的这么一个操作。 there is an operation to reset the loser tree.
我们来看，就是初始化败方树的这样一个过程。 Let us look at the process to initialize the loser tree.
最开始呢，是一些边界的判断，以及我们计算相关的，这个参数。 Well, at the beginning, there needs to determine the border, and we calculate such related parameters.
然后，我们从底层开始比赛。， And then, we start the race from the bottom. That ,
这一次的循环，就是对这个底层的这些结点对呢，进行比赛。 This time of the cycle is a game between node pairs on the bottom.
如果是， That we ,
n为奇数的情况，就会要安排一次内部结点和外部结点的比赛。 if n is an odd number, you will have to arrange a match between internal nodes and external nodes .
而且，我们这个步长的变化呢，要注意特殊处理一下。 and we need special treatment about the change of step.
这一轮，这个，循环，是对剩余的外部结点，也就是，这个倒数第二层 this circle is about the remaining nodes, that is , the penultimate layer.
的这些外部结点，进行比赛。那我们再来看一下比赛的这个函数，Play。 Then we take another look at the function of the game , Play.
我们已经知道，当前的这个， Well, we already know ,this current ,
左右子孩子，然后我们在这个P结点，我们来进行比赛。 left and right children, then we have to compete at the P node.
我们把这个败者，就放在这个P结点这，这个是父结点。 Well, we put this , losers in the P node, this is the parent node.
然后，我们这个胜者，先给它存到一个临时的temp里面。 And then, the winner is saved into a temporary "temp".
然后我再看，我如果是从右边来的，也就说左边都比完了， Then let us look at again, If I was coming from the right, the left is over,
这个时候呢，我应该是采用了这么一个败者树的一个结构。 at this time, I should using such a loser tree structure.
它的一个临时的全局的胜者呢，它也是放在这个，祖父这个位置。 Well, the temporary global winner of is also placed in this, his grandfather, position.
这个时候呢，我要，跟这个当前从右边来的这个位置的，这个结点，我要去跟，这个，祖父再去进行比较。 Well, at this time, the current coming from the right, is going to compare with grandfather again.
然后把这个败者，还是放在祖父这个位置。 And then, put this loser in this position of grandfather.
然后胜者，我们要继续往上面传递，而且， Then the winner of it, we have to continue to pass on above and then
当前这个父结点这，我是给它除2，就变成了祖父。 this current parent node, I give it except two , it becomes a grandfather.
如果是，这一轮比赛都完了以后，那就是说， If this round is over, that is to say ,
从左边来的啦，这个时候我可以停止了。 the one comes from the left, at this time I can stop it.
我就把这个，你前面比赛的这样一个局部的最优呢， I put this, a local optimum in the front match,
我放到祖父这个位置，那就等着后面从右边来的继续跟它比。 in the position of my grandfather, then waiting to continue to compare from the right.
那我们可以看，这样的一个败者树的比赛，它是， Then we can see , such a game of the loser tree, it is,
从左到右，那两个外部结点，一对，然后一刀一刀地这样地切过来的。 left to right, the two external nodes become one pair, and then this cut over here.
如果切到右边的时候，它要对前面的这个结果负责。一直要比到它自己， If it cuts to the right, it is responsible for this result until its own,
从这个右路分支一直往上面走，走到最左那个，就是再没有可能再往右边来的了， from this right branch up to walk on, until the leftmost, that is, no longer possible to go to the right,
才停止。那我们可以看一下这个重构的过程。 It stops. You can look at this reconstruction process.
重构，是非常简单的。我们，首先是判断这样的一个边界条件， reconstruction is very simple. Now, the first is to determine such a boundary condition.
以及去寻找我当前需要重构的这个 i 结点， 它的父结点。 and find the parent node of such i that needs to reconstruct.
然后，我们沿着这个路径往上去比赛。那这个比赛， And we go along this path up to play the game.
那这个比赛，我只需要跟我那个父结点进行比较，不需要去看， For this game, I just need to compare the parent node,
我是要看左兄弟呢，还是要看右兄弟。 and do not need to decide between left brother and right brother.
比的过程，也还是我们把这个，失败的这一个结点呢， That, over the course, still we put, this failed node,
我给它放到这样的一个 祖父结点这。然后我把这个胜利的这个结点，我给它 into the grandfather nodes. Then I put this winner node,
干脆放在B【0】这块。那因为我们反正刚才这个B【0】全局最优已经出列了， in the B[0]. Anyway, because the global optimal at B[0] has been out of the line,
然后我们现在的目的就是整体地， Then our present aim is to,
得到一个正确的B【0】，所以我就用B【0】作为这样一个临时量。 Get a correct B [0] , so I used B [0] as such a temporary variable.
那外排序的效率，我们主要是看， For the efficiency of the external sort, we are mainly looking at
它最开始有几个初始顺串， how many initial strings there are
然后还有，你是能够同时处理多少个顺串。 and how many you are able to simultaneously deal with.
也就是，我们刚才败方树的这个外部结点你可以有多少个？ That is, in the loser tree, how many external nodes you can have?
我们认的归并趟数呢，就会是log以k为底m的对数。 We think the times of merging would be to k log logarithm to the base of m.
显然我们如果是能够减少初始顺串的个数m， It is clear that if we are able to reduce the number of initial string m,
假设你能减到1，我就不需要进行这样的， if you can reduce to one, then I do not need to do this multiple-way merge like this,
多趟的这个归并，1次它就已经是了，对吧？ one time is enough, right?
增加归并的这个顺串数量k， what's else, increasing the number of merging strings k,
也就是刚才这样的一个败方树的外部结点的个数。 That is just the number of external nodes in such a loser tree.
都可以使得这个log，以k为底m的对数变小，那整体的效率会更高。 Well, you can make this , k log logarithm to the base of m smaller, and that the overall efficiency will be higher.
顺串进行归并操作， Well, do the merge operations to the string.
如果我们归并以后整体的这个文件长度是n， After this , if overall length of file is n,
如果我们不采用这样的一个败方树的方法， That if we do not adopt such a loser tree method
我一个一个地看谁最小， Well, I'm comparing one by one to see who is smallest,
那会是，k乘以n这样的代价。 that would be, the cost of k multiplied by n.
如果我们采用败方树的方法呢，因为我是有这个 k路， That if we adopt the loser tree approach, because I have this, k -way ,
这样的话呢，我这个树的高度只是log K 级的。 In this case, the height of the tree is the level of log K.
因此，我们是会把它优化为k加上n乘以logk 这样的一个时间代价。 So we 'll optimize it until k plus n times the log k such a time cost.
因此，采用败方树它是， So using the loser tree
比你这种原始的，挨个找最优，肯定是有很大的改进。 has, of course, a big improvement than this original finding the best one by one.
我们，因为这些顺串它的长度是不一样的， As the length of these strings is not the same,
如果你要在构建这样的一个败方树的过程中， in the process of merge.
其实是需要规划你先合并哪几个，再合并哪几个。 in fact, you need to plan, which combined first and which later.
这个过程就是一个，k路哈夫曼树的一个规划的过程。我们可以看到， Well, this process is a process of planning k-way
左边这个就比右边这个，它的代价要大。 Huffman tree. Well, we can see that the cost of the left is greater than the right.
最后，我们留几个思考。 finally, let's leave some thinking questions.
首先就是，是不是可以用赢者树或者是败方树来形成初始的顺串？ First of all, is it possible to form the initial string with the winner or the loser tree?
另外，我们是不是可以用堆来进行多路归并， In addition, are we able to use heap to do the multiple-way merge
而不是用赢者树和败方树？ instead of winner or loser tree?
好，谢谢大家。 Well, thank you.