algorithm - 从 1,000,000 个总值中找出最大的 10,000 个

Question

我有一个包含 1,000,000 个浮点值的文件。我需要找到 10,000 个最大值。

我在想:

1. 阅读文件
2. 将字符串转换为 float
3. 将 float 放入最大堆(最大值为根的堆)
4. 在所有值都在堆中之后，删除根 10,000 次并将这些值添加到列表/数组列表中。

我知道我会拥有

1. 1,000,000 次插入到堆中
2. 从堆中移除 10,000 次
3. 10,000 次插入到返回列表中

这是一个好的解决方案吗？这是家庭作业。

Answer 1

您的解决方案基本不错。它基本上是一个 heapsort在获得 K 个元素后停止，这将运行时间从 O(NlogN)(对于完整排序)提高到 O(N + KlogN)。这里 N = 1000000，K = 10000。

但是，您最初不应该对堆进行 N 次插入，因为这将花费 O(NlogN) - 相反，使用 heapify 操作在线性时间内将数组转换为堆。

如果这K个数不需要排序，可以用selection algorithm在线性时间内找到第K大的数，然后输出所有比它大的数。这给出了一个 O(n) 解决方案。