40. 最小的 K 个数

文档摘要

最小的 K 个数题目链接牛客网解题思路大小为 K 的最小堆复杂度：O(NlogK) + O(K) 特别适合处理海量数据维护一个大小为 K 的最小堆过程如下：使用大顶堆。在添加一个元素之后，如果大顶堆的大小大于 K，那么将大顶堆的堆顶元素去除，也就是将当前堆中值最大的元素去除，从而使得留在堆中的元素都比被去除的元素来得小。应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。 Java 的 PriorityQueue 实现了堆的能力，PriorityQueue 默认是小顶堆，可以在在初始化时使用 Lambda 表达式 (o1, o2) -\> o2 - o1 来实现大顶堆。其它语言也有类似的堆数据结构。