排序1万亿整数

Question

给定硬盘上的1万亿个整数,找到最小的100万个整数.一次最多可以在内存中容纳100万个整数.

一种方法是,从1万亿中取出前100万个并对100万个整数进行排序并将其存储回硬盘中.通过这种方式对每组100万个整数进行排序并将其存储在硬盘中.现在,100万个整数的组合分类达1万亿.现在比较所有排序组的第一个元素,它们的最小值是1万亿的最小值.将其存储为内存中的第一个元素.接下来,从最小元素所在的组中取出第二个元素,然后使用所有其他组的第一个元素进行检查.以这种方式重复该过程,直到第一个100万被分类并存储在存储器中.

我缺少一种更优化的方法吗？

Answer 1

您可以使用堆在O(n log m)中有效地执行此操作.(n =所有数字,m =您要查找的数字集的大小).

一次通过一万亿个数字.对于每个新号码,请执行以下操作之一.

1. 如果堆有<1百万个节点,则将新数字插入堆中.
2. 如果堆只有100万个节点且顶部节点大于新数字,则从堆中弹出顶部节点,然后插入带有新编号的节点.
3. 如果1或2都不是真的那么扔数字.

在完成所有万亿条目后,生成的堆将拥有100万个最小的数字.

从堆中插入和删除是O(log m).通过堆的单次传递是n.所以,算法是n*log(m)