algorithm - 用堆进行外部排序？

Question

我有一个包含大量数据的文件，我想在任何给定时间对其只包含内存中的一小部分数据进行排序。

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

我主要了解堆，并且了解堆化数据会将其按适当的顺序排列，从中我可以将它的最后一部分作为我的解决方案，但我无法弄清楚如果没有每个奇怪的项目的 I/O。

想法？

谢谢! :D

Answer 1

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

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

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

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