关于TOP K 问题
来源：8-7 Leetcode上优先队列相关问题
ForsunFor
2020-03-05
在数组中寻找第K大的元素，我看很多方法都是用老师的这种方法，复杂度是 O(nlogK)。
我想的是，是不是可以对数组进行 heapify 把数组先变成一个堆，复杂度是 O(n)，
然后再依次取出K个元素，复杂度是 O(klogn)，合起来就是 n + klogn。
不知道这个方法的 n + klogn，是不是要比 nlogk 要好？
1回答
-
对于你的方法，如果 k 很小，是的，你的方法更好。
甚至，这个问题有一个 O(n) 级别的解决方案，即利用快排的 partition 的原理，可以在 O(n) 级别解决这个问题。我在我的课程《数据结构与算法》中，提供过一版这个思路的补充代码，可以参考这里：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-05-Selection/main.cpp
但是，使用优先队列的最重要的优势是：我们不需要初始知道所有数据，就可以开始处理。数据可以以数据流的形式慢慢流入堆中，我们的堆只保持 k 个元素就好了。
这个特点在很多时候都有用，最典型的情况是大数据，比如 1 T 的数据，不可能把所有数据都装进内存，然后做 heapify，怎么办？这个方法不需要那么大的内存。从文件里一点一点读数据，流入这个堆就好了。
再比如，有的情况下，数据本身就是逐渐形成的，而不是一次性摆在那里。比如购物网站实时统计每天单笔最大的 k 个订单，如果等一天的订单都产生，再 heapify，就不实时了。使用这个方法，每出现一笔新的订单，和堆中的数据比较一次。堆中存储的，就是实时的情况。
数据结构关键的优势还是在于动态。对于这一点，印象中课程也有所强调，以后随着工程经验的增多，慢慢会对此理解越来越深刻的：）
继续加油！：）
222020-03-05
相似问题