🏆

Top K Elements — Min-Heap of Size K

Keep a min-heap of exactly K elements. For each new number: offer(num), if size > K then poll() (drop smallest). After all elements, peek() = Kth largest.

🔢 Min-Heap Size K ⚡ O(n log k) 🎯 Kth Largest Time O(n log k) Space O(k)

📋 When to Use

Kth largest element — min-heap of size K, peek() = answer
Top K frequent — min-heap ordered by frequency
K closest points — max-heap on distance, size K
New element > heap.peek() → it joins top K, displacing the current Kth
New element ≤ heap.peek() → discard, it's too small for top K

💡 The min-heap root is always the smallest of the top-K, which is the Kth largest overall. This is the key invariant — the heap holds exactly the K largest elements seen so far.

⚡ Complexity

Time

O(n log k)

Space

O(k)

Each of n elements: offer + optional poll = O(log k).
Heap stays at most size K → O(k) space.
Compare: sorting = O(n log n) time, O(n) space.
Quickselect: O(n) avg time, but O(n) space & modifies array.
Min-heap K wins when K << n and you stream the data.

Problem Given nums = [3,1,5,12,2,11,9,7] and k = 3, find the 3rd largest element. Maintain a min-heap of size K — push each element in; if heap exceeds K, pop the minimum (too small for top K). The heap root is always the K-th largest seen so far.
Input: nums = [3,1,5,12,2,11,9,7], k = 3 · Answer: 9 (top-3 are 12, 11, 9 — heap root = 9)

Step 0 / 9

🔄 Init ➕ Add 📋 Heap Full 💥 Pop Min ⏭ Too Small 🏆 Result

Heap Size0/ K=3

Kth Largest—

nums = [3, 1, 5, 12, 2, 11, 9, 7] · k = 3

🏔️ Min-Heap (size ≤ K) K = 3 ❌ popped: —

— root/min

— left

— right

💡 Key invariant: The heap holds the K largest elements seen so far. The root (minimum of the heap) = the Kth largest.

🏆 Top K Elements: Keep a min-heap of exactly K=3 elements. Scan nums left to right, add each element, pop if size exceeds K. Root always = Kth largest!

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

🧩 Pattern Skeleton Java 8

// Top K Largest — min-heap of size K ─────────────────────────
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) minHeap.poll(); // drop smallest
}
return minHeap.peek(); // peek = kth largest

// Top K Frequent — heap on frequency ─────────────────────────
Map<Integer,Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<Integer> pq = new PriorityQueue<>(
    (a,b) -> freq.get(a) - freq.get(b));  // min by frequency
for (int key : freq.keySet()) {
    pq.offer(key);
    if (pq.size() > k) pq.poll();
}
// remaining k entries = top k frequent

🎯 Practice Problems

#215Kth Largest Element in Array 🏆 min-heap kMedium #347Top K Frequent Elements 📊 freq map + heapMedium #973K Closest Points to Origin 📍 max-heap on distanceMedium #1046Last Stone Weight 💎 max-heap simulationEasy #378Kth Smallest Element in Sorted Matrix 🔢 min-heap + matrixMedium #692Top K Frequent Words 📝 freq heap + lexicographicMedium