如果有一个数字流,您如何跟踪第1,000,000个最大的数字？

Question

如果有一个数字流,您如何跟踪第1,000,000个最大的数字？

我在接受采访时被问到这个问题.

Answer 1

一种方法是保持最小堆,并将堆的大小限制为1,000,000.虽然堆没有达到1,000,000个项目,但我们会将流中的每个新项目添加到堆中.当堆变满时,我们会将流中的每个新项目与堆中的最小项进行比较,如果它大于最小值,我们将弹出最小项并插入新项.这样,堆的最小项始终是第1,000,000个最大值.

伪代码示例:

Handle_Stream_Item(item):
  if(MinHeap.size < 1000000):
    MinHeap.insert(item)
  else if (item > MinHeap.min()):
    MinHeap.extractMin()
    MinHeap.insert(item)