找出1,000,000总价值中最大的10,000个

Question

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

我在考虑:

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

我知道我会的

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

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

Answer 1

你的解决方案非常好.它基本上是一个在获得K元素后停止的堆,它可以改善从O(NlogN)(完整排序)到的运行时间O(N + KlogN).这里N = 1000000且K = 10000.

但是,您最初不应该对堆执行N次插入,因为这样做O(NlogN)- 而是使用heapify操作,该操作在线性时间内将数组转换为堆.

如果不需要对K数进行排序,则可以使用选择算法找到线性时间内的第K个最大数,然后输出大于它的所有数.这给出了O(n)解决方案.