algorithm - 在十亿的文件中找到一百个最大的数字

Question

我今天去面试，被问到这个问题:

Suppose you have one billion integers which are unsorted in a disk file. How would you determine the largest hundred numbers?

我什至不确定我该从哪里开始回答这个问题。给出正确结果的最有效过程是什么？我是否需要遍历磁盘文件一百次以获取列表中尚未出现的最高数字，还是有更好的方法？

Answer 1

显然，面试官希望您指出两个关键事实:

• 您无法将整个整数列表读入内存，因为它太大了。所以你必须一一阅读。
• 您需要一个高效的数据结构来保存 100 个最大的元素。该数据结构必须支持以下操作:
  • Get-Size : 获取容器中值的个数。
  • Find-Min : 取最小值。
  • Delete-Min : 删除最小值以用更大的新值替换它。
  • Insert : 向容器中插入另一个元素。

通过评估数据结构的要求，计算机科学教授希望您推荐使用 Heap (最小堆)，因为它旨在支持我们在这里需要的操作。

例如，对于 Fibonacci heaps , 操作 Get-Size , Find-Min和 Insert都是O(1)和 Delete-Min是O(log n) (在本例中为 n <= 100)。

在实践中，您可以使用您最喜欢的语言的标准库中的优先级队列(例如，C++ 中的 priority_queue 中的 #include <queue>)通常使用堆来实现。