Definition
- Min-heap of size K – the root is the smallest of the K numbers currently kept, making the keep-or-discard decision a single O(1) peek.
- Eviction rule – a new number enters the heap only if it beats the root; it then replaces the root via poll-then-offer, which is O(log K).
- Counter-intuitive choice – to find the K largest you use a min-heap, not a max-heap, because the root being the smallest of the kept set is what lets you cheaply evict the weakest candidate.
- Streaming friendly – each element is processed once without needing the full array in memory.
- O(n log K) time – each of the n elements costs at most O(log K) for a heap operation.
At the National Bank of India, transaction amounts arrive all day and the risk team wants the K biggest transactions for priority review. They keep a small bucket that holds only the K biggest so far, where the smallest of those K sits at the top for quick checking. Each new transaction only enters the bucket if it beats the smallest one currently in it, pushing that smallest one out.
Understanding the Concepts
What is the Top K Numbers problem?
Given an unsorted array of numbers and a value K, find the K largest numbers. The result does not need to be sorted. This is the foundational Top K Elements problem that appears in many variations: top K frequent, top K closest, and K-th largest.
package com.bank.risk;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class TopKFinder {
public static List<Integer> findTopK(int[] amounts, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int amount : amounts) {
if (minHeap.size() < k) {
minHeap.offer(amount);
} else if (amount > minHeap.peek()) {
minHeap.poll();
minHeap.offer(amount);
}
}
return new ArrayList<>(minHeap);
}
}
Why use a min-heap instead of a max-heap?
The counter-intuitive choice is that to find the K largest numbers, you use a min-heap, not a max-heap. The root of the min-heap is the smallest of the K numbers you are currently keeping. This means the root is the weakest candidate in your kept set, so deciding whether a new number deserves a place is a single O(1) peek: if the new number is larger than the root, it replaces the root. If you used a max-heap, the root would be the largest kept number, and you would have no efficient way to find and evict the weakest.
package com.bank.risk;
public class WhyMinHeap {
public static void explain() {
// Min-heap of size 3, holding [5, 8, 10]
// Root = 5 (smallest of the 3 largest)
// New number 7: 7 > 5? Yes -> evict 5, insert 7
// Heap becomes [7, 8, 10]
// New number 3: 3 > 7? No -> discard
// Heap stays [7, 8, 10]
// If we used a max-heap of size 3, root = 10
// New number 7: is it one of the top 3? We cannot tell from the root!
// We would need to inspect all elements -> defeats the purpose
}
}
How does the keep-or-discard decision work?
For the first K elements, push them all into the heap to fill it to size K. For each subsequent element, compare it with the heap root (the smallest of the K largest). If the new element is larger, poll the root and offer the new element. If it is smaller or equal, discard it. After processing all elements, the heap contains exactly the K largest numbers.
package com.bank.risk;
import java.util.PriorityQueue;
public class KeepOrDiscard {
public static void trace() {
int[] amounts = {100, 500, 200, 800, 300, 900, 150};
int k = 3;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Fill first K=3: heap = [100, 500, 200] -> root = 100
// 800 > 100: evict 100, insert 800 -> heap = [200, 500, 800] -> root = 200
// 300 > 200: evict 200, insert 300 -> heap = [300, 500, 800] -> root = 300
// 900 > 300: evict 300, insert 900 -> heap = [500, 800, 900] -> root = 500
// 150 < 500: discard
// Final: [500, 800, 900] = top 3 largest
for (int amount : amounts) {
if (minHeap.size() < k) minHeap.offer(amount);
else if (amount > minHeap.peek()) {
minHeap.poll();
minHeap.offer(amount);
}
}
System.out.println("Top 3: " + minHeap);
}
}
Top 3: [500, 800, 900]
What is the time and space complexity?
Time is O(n log K). Each of the n elements costs at most one peek (O(1)) and one poll-plus-offer (O(log K)). When K is much smaller than n, this is significantly better than O(n log n) sorting. Space is O(K) for the heap.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Sort then take last K | O(n log n) | O(1) or O(n) | Simple but slower |
| Min-heap of size K | O(n log K) | O(K) | Optimal for small K |
| Quickselect | O(n) average | O(1) | Best average but O(n^2) worst |
| Max-heap of all elements | O(n + K log n) | O(n) | Wastes space |
How does this compare to quickselect?
Quickselect finds the K-th largest in O(n) average time but O(n^2) worst case. The min-heap approach guarantees O(n log K) worst case. For streaming data where elements arrive one at a time, quickselect is not applicable because it requires the full array, while the heap processes each element as it arrives.
package com.bank.risk;
public class QuickSelectComparison {
// Quickselect: requires full array, O(n) average, O(n^2) worst
// Min-heap: streaming, O(n log K) guaranteed
// When to use which:
// - Full array available, need K-th element: quickselect
// - Streaming data, need top K: min-heap
// - Need guaranteed worst case: min-heap
// - K is close to n: sorting may be simpler
}
What about the K smallest (symmetric problem)?
By symmetry, to find the K smallest numbers, use a max-heap of size K. The root is the largest of the K smallest numbers. A new number replaces the root only if it is smaller. The same O(n log K) time and O(K) space apply.
package com.bank.risk;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class BottomKFinder {
public static List<Integer> findBottomK(int[] amounts, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int amount : amounts) {
if (maxHeap.size() < k) {
maxHeap.offer(amount);
} else if (amount < maxHeap.peek()) {
maxHeap.poll();
maxHeap.offer(amount);
}
}
return new ArrayList<>(maxHeap);
}
}
What are edge cases?
Edge cases include K equal to zero (return empty), K equal to n (return all elements), K greater than n (return all elements), and an array with duplicate values.
package com.bank.risk;
import java.util.List;
public class EdgeCases {
public static void test() {
System.out.println(TopKFinder.findTopK(new int[]{5, 3, 8}, 0)); // []
System.out.println(TopKFinder.findTopK(new int[]{5, 3, 8}, 3)); // [3, 5, 8]
System.out.println(TopKFinder.findTopK(new int[]{5, 5, 5}, 2)); // [5, 5]
}
}
What should a senior engineer know?
A senior engineer should mention that for very large K close to n, sorting is simpler. For distributed systems, each machine can maintain its own top-K min-heap and the results can be merged by inserting all candidates into a final size-K min-heap. For real-time dashboards at scale, approximate algorithms like count-min sketch can provide top-K estimates with bounded error.
// Senior considerations:
// 1. K close to n: just sort, simpler code
// 2. Distributed top-K: each node keeps size-K heap, merge at coordinator
// 3. Real-time approximate: count-min sketch + min-heap
// 4. Thread safety: wrap heap in synchronized block or use concurrent structure
// 5. Banking: use BigDecimal for amounts, Comparator.reverseOrder() for max-heap
Visual Overview
Min-Heap Top K Flow
====================
Stream: [100, 500, 200, 800, 300, 900, 150] K=3
Step 1: Fill heap to size K
100 → heap=[100]
500 → heap=[100, 500]
200 → heap=[100, 500, 200] root=100
Step 2: Keep-or-discard for remaining
800 > 100? Yes → evict 100
heap=[200, 500, 800] root=200
300 > 200? Yes → evict 200
heap=[300, 500, 800] root=300
900 > 300? Yes → evict 300
heap=[500, 800, 900] root=500
150 > 500? No → discard
Final heap: [500, 800, 900] = Top 3
Heap Structure
==============
Min-Heap (size K=3):
┌───┐
│500│ ← root (smallest of top 3)
└─┬─┘
┌──┴──┐
┌──┴─┐ ┌─┴──┐
│800 │ │900 │
└────┘ └────┘
New number arrives:
┌─────────────────────┐
│ num > root (500)? │
├──────┬──────────────┤
│ Yes │ No │
│ Evict│ Discard │
│ root │ num │
└──────┴──────────────┘
Key Takeaway
Top K Numbers is the foundational Top K Elements problem, and the counter-intuitive choice is that to find the K largest numbers you use a min-heap, not a max-heap. You keep the heap bounded to size K and seed it with the first K numbers. For every remaining number, you compare it against the heap root, which is the smallest of the K numbers you are currently keeping. If the new number is larger, you evict the root and insert the new number; if not, you discard it.
The reason the min-heap works is that the root is always the weakest candidate in your kept set, so deciding whether a new number deserves a place is a single constant-time peek, and eviction is one O(log K) heap operation. This gives O(n log K) time and O(K) space, which is far better than O(n log n) sorting when K is small relative to n.
At the National Bank of India, Rajesh used this to pull the K largest transaction amounts from a long daily stream for the risk team's priority review. He kept a size-K min-heap where each new amount only displaced the smallest kept amount if it was larger, processing millions of transactions without sorting them all.
The senior-level insight is understanding when to switch tools: quickselect gives O(n) average for a static array, sorting is simpler when K is close to n, and in distributed systems each node keeps its own top-K heap and results are merged at a coordinator.
Remember one sentence: min-heap of size K, evict the root only when a larger number arrives, and the heap always holds the K largest.
---