当数据是流的形式 解决top k 和 select k 快排还是优先队列

老师你好，对于“每来一笔订单，排一次，太慢”这句话，我是这样理解的。

当产生一笔新订单时，

对于快排，需要将新的订单和之前所有订单看做一个数组进行排序，每次partition确定一个有序点后，该有序点与K比较大小，根据情况综合来看下一次partition需要处理的范围会缩小一半，等比数列求和后时间复杂度为o(n)

对于优先队列，新订单加入堆对应一次shiftUp操作(选用shiftUp因为动态数组addLast时间复杂度0(1))，时间复杂度o(logn)。取出最大值对应一次shiftDown操作，时间复杂度o(logn),综合时间复杂度 o(logn)

整体来看  o(n) > o(logn),所以使用优先队列解决 来一笔新订单 获取最大值的操作开销更小。

老师，请问我这样理解对吗

理解的是正确的。

其实如果每次来一个数据点，并不需要做排序操作，因为之前的数据是已经排好序的，只需要找到新的位置做插入就好，时间复杂度是 O(n) 的。

这里的关键是，O(logn) 是远远低于 O(n) 的，而不是简单的开销小一点。这是我一直在课程中强调，并实验的内容。

如果 n = 100 万，logn 只有 6，他们之间相差 10 万倍。这意味着如果 logn 的算法执行需要 1s 的话，O(n) 的算法要执行一天多。

如果 n = 10 亿，logn 只有 9，他们之间相差 1 亿倍。这意味着如果 logn 的算法执行需要 1s 的话，O(n) 的算法需要执行 3 年多。

继续加油！：）