🏆 Top K Elements

Why Heap? The Key Insight

Sorting approach: O(n log n) - sorts all n elements

Heap approach: O(n log k) - maintains only k elements!

When k << n, this is MUCH faster. Example: Find top 10 from 1 million items.

// Kth Largest Element
function findKthLargest(nums, k) {
    // Use min-heap of size k
    const minHeap = new MinHeap();
    
    for (let num of nums) {
        minHeap.push(num);
        
        // Keep heap size = k
        if (minHeap.size() > k) {
            minHeap.pop(); // Remove smallest
        }
    }
    
    // Root of min-heap = kth largest
    return minHeap.peek();
}

Min-Heap vs Max-Heap: When to Use

• K Largest elements: Use Min-Heap (remove smallest when size > k)
• K Smallest elements: Use Max-Heap (remove largest when size > k)
• Why counterintuitive? We remove opposite elements to keep the K we want!

Top K Frequent Elements

function topKFrequent(nums, k) {
    // Step 1: Count frequencies
    const freq = {};
    for (let num of nums) {
        freq[num] = (freq[num] || 0) + 1;
    }
    
    // Step 2: Use min-heap of size k
    const minHeap = new MinHeap((a, b) => a[1] - b[1]);
    
    for (let [num, count] of Object.entries(freq)) {
        minHeap.push([num, count]);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    // Step 3: Extract elements
    return minHeap.toArray().map(x => x[0]);
}

Real-World Applications

• Leaderboards: Gaming (top 100 players), sports rankings
• Recommendation Systems: Netflix top 10, YouTube trending
• Search Engines: Google top search results
• E-commerce: Amazon best sellers, trending products
• OS Task Scheduling: Priority queues for processes
• Network Routing: Shortest path algorithms (Dijkstra)