从N个元素中维护前M个元素的疑问

Question

老师，疑问是这样的，从100个数字中提取前10个大的数?
ok, 按照本次优先队列的作法，当不足10个元素时，堆里持续添加数字，直到10个，此时，大堆中刚好有10个数字，堆顶就是最大值
那么接下来，我来取第11个数，假定这个数比堆顶大，ok, 取出当前的堆顶数字，然后将第11个数字放入堆中。如果这个数比堆顶小，那为什么不作行动呢，因为它只是比堆顶小，但是它完全有可能比非堆顶的值大呀，这就是我的疑问：）

Answer 1

liuyubobobo 2019-06-15 00:32:59

从100个数字中提取前10个大的数，要使用最小堆，最小堆中存放当前找到的最大的10个数。

如果新的数字比堆顶小，就比堆中所有元素小，扔掉；

如果新的数字比堆顶大，我们就将堆顶元素拿走，新数字入堆，以此维护堆中是当前找到的最大的10个元素：）

继续加油！：）

• 提问者 甲骨文_0001 #1

  老师，晚安, 非常感谢！