Keep a small heap of size k while scanning the data. The heap root is always the weakest of your current top k, so it is the one to replace.
Used for
weakest = 1
3 > 1: replace
7 > 3: replace
2 < 5: skip
The club is 5, 7, 9 and the next number is 8. What happens?
Not quite. 8 beats the weakest member (5), so 5 is replaced. The club becomes 7, 8, 9.
Step 1 of 6
Goal: find the 3 biggest numbers. Sorting everything works but does more than needed. Instead keep a small club of the best 3 so far and always know its weakest member, the first to be kicked out. (A min-heap gives you the weakest in one step.)
Step 2 of 6
Take in 5, 1 and 9. The club is full: 1, 5, 9. The weakest member is 1.
Step 3 of 6
Next is 3. It beats the weakest (1), so 1 leaves and 3 joins: 3, 5, 9.
Step 4 of 6
7 beats the new weakest (3). Club: 5, 7, 9.
Step 5 of 6
2 is smaller than the weakest (5), so ignore it. The club is the answer: 5, 7, 9. Each number costs one quick heap update, about n log k steps in all. This is the Top K pattern.
Step 6 of 6
Your turn.
k-Nearest Neighbors AlgorithmHeap (data-structure)Priority QueueHeap Sort
// Keep a min-heap of size k: its root is the kth largest.// JS has no built-in heap, so use MinHeap from the Heap topic.function kthLargest(nums, k, MinHeap) { const h = new MinHeap(); for (const n of nums) { h.add(n); if (h.heapContainer.length > k) h.poll(); } return h.peek();}