堆排序及堆的应用

甚至源源不断到来，但需要知道目前为止前 K 个最大或最小的元素。当然问题还可能变为求解 第 K 个 最大的元素或最小的元素。

通常我们有如下解决方案：

1. 使用JDK中自带的排序，如 Arrays.sort() ，由于底层使用的快速排序，所以时间复杂度为 O(nlogn) 。但是如果 K 取值很小，比如是 1，即取最大值，那么对所有元素排序就没有必要了。
2. 使用简单选择排序，选择 K 次，那么时间复杂度为 O(n*K) ，如果 K 大于 logn，那还不如快排呢!

上述两种思路都是假定所有元素已知，如果元素个数不确定，且数据源源不断到来的话，就无能为力了。

下面提供一种新的思路：

我们维护一个长度为 K 的数组，最前面 K 个元素就是目前最大的 K 个元素，以后每来一个新元素，都先找数组中的最小值，将新元素与最小值相比，如果小于最小值，则什么都不变，如果大于最小值，则将最小值替换为新元素。这样一来，数组中维护的永远是最大的 K 个元素，不管数据源有多少，需要的内存开销都是固定的，就是长度为 K 的数组。不过，每来一个元素，都需要找到最小值，进行 K 次比较，是否有办法能减少比较次数呢?

当然，这时候堆就要登场了，我们使用最小堆维护这 K 个元素，每次来新的元素，只需要和根节点比较，小于等于根节点，不需要变化，否则用新元素替换根节点，然后 siftDown 调整堆即可。此时的时间复杂度为 O(nlogK) ，相比上述两种方法，效率大大提升，且空间复杂度也大大降低。

Top K 问题代码：


 

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!