Fundamentals · Hard · Free
What is a heap? How does a priority queue help in Top K problems?
FresherFundamentalsData Structures & Algorithms
Heap & Top K
Min-heap root is smallest—O(log n) insert/extract. For Top K largest, use size-k min-heap.
java
int[] topK(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : nums) {
pq.offer(x);
if (pq.size() > k) pq.poll();
}
return pq.stream().mapToInt(i -> i).toArray();
}Complexity: O(n log k)—better than sort entire array when k ≪ n.