我有一个包含大量数据的文件，我想在任何给定时间对它进行排序，仅保留内存中的一小部分数据。
我已经注意到，合并排序是流行的外部排序，但我想知道它是否可以用堆(最小或最大)。基本上，我的目标是在100个项目列表中获得顶部(使用任意数字)10个项目，同时在内存中永远不超过10个项目。
我主要理解堆，并理解堆积数据将把它放在适当的顺序，从中我可以把它的最后一部分作为我的解决方案，但我不知道如何做没有I/O为每一个该死的项目。
想法?
谢谢!: D
使用堆排序需要在文件中进行大量的查找操作，以便在初始创建堆时以及在删除顶部元素时进行查找操作。因此，这不是一个好主意。
但是，您可以使用归并排序的变体，其中每个堆元素都是一个排序列表。列表的大小取决于您希望在内存中保留多少。通过加载数据块，对它们进行排序，然后将它们写入临时文件，可以从输入文件中创建这些列表。然后，将每个文件视为一个列表，读取第一个元素并从中创建堆。当移除顶部元素时，您可以将其从列表中移除，并在必要时恢复堆条件。
有一个方面使得这些关于排序的事实无关紧要:你说你想确定前10个元素。为此，您确实可以使用内存堆。只需从文件中取出一个元素，将其推入堆中，如果堆的大小超过10，则删除最小的元素。为了提高效率，只有在大小低于10或高于最低元素时才将其推入堆中，然后替换并重新堆化最低元素。将前十位保存在堆中允许您只扫描一次文件，其他所有内容都将在内存中完成。使用二叉树而不是堆也可以工作，并且可能同样快速，对于像10这样的小数字，您甚至可以使用数组并对元素进行冒泡排序。
注意:我假设10和100只是例子。如果您的数字真的很低，那么任何关于效率的讨论都可能是没有意义的，除非您每秒执行此操作数次。
是的，您可以使用堆来查找大文件中的top- k项，仅在内存中保留堆+ I/O缓冲区。
下面将利用长度为k的最大堆获得最小k项。您可以顺序读取文件，对每个项执行I/O操作，但是将数据块加载到长度为b的辅助缓冲区中通常要快得多。该方法使用O(k + b)空间在O(n*log(k))操作中运行。
while (file not empty)
read block from file
for (i = all items in block)
if (heap.count() < k)
heap.push(item[i])
else
if (item[i] < heap.root())
heap.pop_root()
heap.push(item[i])
endif
endfor
endwhile
堆需要大量的非顺序访问。归并排序非常适合外部排序，因为它做了大量的顺序访问。
顺序访问在旋转的磁盘上要快得多，因为磁头不需要移动。在固态磁盘上，顺序访问也可能比堆排序访问快得多，因为它们在块中进行访问，可能比文件中的单个内容大得多。
通过使用合并排序并通过引用传递两个值，您只需要在缓冲区中保存两个比较值，并在数组中移动，直到它排序完毕。