(转)算法之优先队列 PriorityQueue解决Top K 问题

(转)算法之优先队列 PriorityQueue解决Top K 问题

转自:https://www.jianshu.com/p/a4a1984fc4ff

解决方法:
维护一个大小为 K 的小顶堆,依次将数据放入堆中,当堆的大小满了的时候,只需要将堆顶元素与下一个数比较:如果大于堆顶元素,则将当前的堆顶元素抛弃,并将该元素插入堆中。遍历完全部数据,Top K 的元素也自然都在堆里面了。

当然,如果是求前 K 个最小的数,只需要改为大顶堆即可

将数据插入堆 95 大于 20,进行替换 95 下沉,维持小顶堆
对于海量数据,我们不需要一次性将全部数据取出来,可以一次只取一部分,因为我们只需要将数据一个个拿来与堆顶比较。

另外还有一个优势就是对于动态数组,我们可以一直都维护一个 K 大小的小顶堆,当有数据被添加到集合中时,我们就直接拿它与堆顶的元素对比。这样,无论任何时候需要查询当前的前 K 大数据,我们都可以里立刻返回给他。

整个操作中,遍历数组需要 O(n) 的时间复杂度,一次堆化操作需要 O(logK),加起来就是 O(nlogK) 的复杂度,换个角度来看,如果 K 远小于 n 的话, O(nlogK) 其实就接近于 O(n) 了,甚至会更快,因此也是十分高效的。

最后,对于 Java,我们可以直接使用优先队列 PriorityQueue 来实现一个小顶堆,这里给个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<Integer> solutionByHeap(int[] input, int k) {
List<Integer> list = new ArrayList<>();
if (k > input.length || k == 0) {
return list;
}
Queue<Integer> queue = new PriorityQueue<>();
for (int num : input) {
if (queue.size() < k) {
queue.add(num);
} else if (queue.peek() < num) {
queue.poll();
queue.add(num);
}
}
while (k-- > 0) {
list.add(queue.poll());
}
return list;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×