外部排序归并时，使用败者树还是最小堆？

Question

背景

外部排序的介绍，参考资料：外部排序wiki介绍。

实际上，中文wiki上的介绍中，直接使用了最小堆来做排序后的多个子文件的归并，以得到最终的排序序列。而在我看到的很多网上资料上，却是介绍使用败者树，比如如下链接： 链接1、 链接2、 链接3。

我的理解

按照我的理解，最小堆实现和败者树实现理应在时间复杂度和空间复杂上差不多（虽然败者树需要额2k的空间，而最小堆本身只需要k的空间，但最小堆每个元素被取出后，还需要确定是从哪个顺串中补充元素，故也需要增加额外的空间标记堆中元素所在的顺串），这两者有什么区别呢，或者如何选择？

PS

实际上，我在网上查阅败者树的资料时，并没有找到英文资料-,-，让我很费解。请大家赐教~

Answer 1

首先感谢楼主给出的连接，学到不少，但我的理解跟你的理解不太一样，外排序分成两部分来实现的，第一部分是将一个大文件分成几个有序的小文件，第二部分是将几个有序的小文件合成一个大的有序文件，维基百科上说的是用最小堆实现的选择置换法来优化第一部分的排序，而其他链接中给的败者树是用来优化第二部分的。你给的第二个链接，我感觉讲的非常到位。仔细阅读下。