从N个元素中维护前M个元素的疑问
来源：8-6 基于堆的优先队列
甲骨文_0001
2019-06-15
老师，疑问是这样的，从100个数字中提取前10个大的数?
ok, 按照本次优先队列的作法，当不足10个元素时，堆里持续添加数字，直到10个，此时，大堆中刚好有10个数字，堆顶就是最大值
那么接下来，我来取第11个数，假定这个数比堆顶大，ok, 取出当前的堆顶数字，然后将第11个数字放入堆中。如果这个数比堆顶小，那为什么不作行动呢，因为它只是比堆顶小，但是它完全有可能比非堆顶的值大呀，这就是我的疑问：）
写回答
1回答
-
从100个数字中提取前10个大的数，要使用最小堆，最小堆中存放当前找到的最大的10个数。
如果新的数字比堆顶小，就比堆中所有元素小，扔掉；
如果新的数字比堆顶大，我们就将堆顶元素拿走，新数字入堆，以此维护堆中是当前找到的最大的10个元素：）
继续加油！：）
312019-06-15
相似问题