用堆进行外部排序？

Question

我有一个包含大量数据的文件，我想对它进行排序，以便在任何给定时间仅将一部分数据保存在内存中。

我注意到合并排序在外部排序中很流行，但是我想知道是否可以使用堆（最小或最大）来完成。基本上，我的目标是在100个项目的列表中获得前10个项目（使用任意数字），同时在内存中保存的项目绝不超过10个。

我最了解堆，并了解堆数据将按适当的顺序排列，从中可以将其最后一部分作为解决方案，但我不知道如何在没有I / O的情况下进行处理。每一个freakin项目。

有想法吗？

谢谢！：D

Answer 1

使用堆排序需要在文件中进行大量查找操作，以便最初创建堆以及删除顶部元素时也是如此。因此，这不是一个好主意。

但是，您可以使用mergesort的变体，其中每个堆元素都是一个排序列表。列表的大小取决于您要在内存中保留多少。您可以通过以下方式从输入文件中创建这些列表：加载数据块，对其进行排序，然后将其写入临时文件。然后，将每个文件视为一个列表，读取第一个元素并从中创建一个堆。删除顶部元素时，可以将其从列表中删除，并在必要时恢复堆条件。

但是，有一个方面使这些有关排序的事实变得无关紧要：您说要确定前10个元素。为此，您确实可以使用内存堆。只需从文件中取出一个元素，然后将其推入堆，如果堆的大小超过10，则删除最低的元素。为了提高效率，仅当大小小于10或大于最低元素时才将其推入堆，然后替换并重新堆化。将前十名保留在堆中仅允许您一次浏览文件，其他所有操作都将在内存中完成。使用二叉树而不是堆也可以，并且可能同样快，对于像10这样的小数目，您甚至可以使用数组并对元素进行冒泡排序。

注意：我假设10和100只是示例。如果您的数量真的那么低，那么除非您每秒执行几次此操作，否则任何有关效率的讨论都可能没有意义。