7a:T47d,The Top-K problem has a deceptively simple formulation: > **Given a collection of n elements, find the K largest (or smallest) elements.** But this simple statement hides considerable depth. Let's formalize it precisely: **Formal Definition:** - **Input:** A collection A of n comparable elements and an integer K where 1 ≤ K ≤ n - **Output:** A set S containing exactly K elements from A such that every element in S is greater than or equal to every element in A − S (for Top-K largest) **Key Observations:** 1. **Order within the K elements may or may not matter.** Some problems ask for just the K elements (unordered), while others want them in sorted order. This affects the final step of your solution. 2. **The Kth largest element has special significance.** It serves as the "threshold"—any element greater than or equal to this value is in the Top-K set. 3. **K is typically much smaller than n.** Most real-world Top-K problems have K << n. If K approaches n, you're essentially sorting the entire collection. 4. **The elements don't need to be distinct.** Duplicates are handled naturally by the algorithms we'll explore.7b:T96f,import heapq from typing import List def top_k_largest(arr: List[int], k: int) -> List[int]: """ Find the K largest elements using a min-heap. Time Complexity: O(n log K) - We process each of n elements exactly once - Each heap operation (insert/extract) is O(log K) - Since heap size never exceeds K, operations are O(log K), not O(log n) Space Complexity: O(K) - The heap stores at most K elements at any time Args: arr: Input array of n elements k: Number of largest elements to find Returns: List of K largest elements (not necessarily sorted) """ if k <= 0: return [] if k >= len(arr): return arr[:] # All elements are in Top-K # Python's heapq is a min-heap by default # We'll use it directly for finding K largest min_heap = [] for element in arr: if len(min_heap) < k: # Phase 1: Fill the heap until we have K elements heapq.heappush(min_heap, element) elif element > min_heap[0]: # Phase 2: New element beats our weakest candidate # heapreplace is more efficient than extractMin + insert heapq.heapreplace(min_heap, element) return min_heap def top_k_smallest(arr: List[int], k: int) -> List[int]: """ Find the K smallest elements using a max-heap. For K smallest, we use a MAX-heap of size K. The max element is our threshold—anything smaller must be in Top-K. Since Python only provides min-heap, we negate values. """ if k <= 0: return [] if k >= len(arr): return arr[:] # Negate values to simulate max-heap max_heap = [] for element in arr: if len(max_heap) < k: heapq.heappush(max_heap, -element) elif element < -max_heap[0]: # Compare with current max heapq.heapreplace(max_heap, -element) # Negate back to get original values return [-x for x in max_heap] # Example usage and verification if __name__ == "__main__": arr = [5, 2, 9, 1, 7, 6, 8] print(f"Array: {arr}") print(f"Top 3 largest: {sorted(top_k_largest(arr, 3), reverse=True)}") print(f"Top 3 smallest: {sorted(top_k_smallest(arr, 3))}") # Output: # Array: [5, 2, 9, 1, 7, 6, 8] # Top 3 largest: [9, 8, 7] # Top 3 smallest: [1, 2, 5]7c:Tc32,/** * MinHeap implementation for Top-K operations. * Most production code would use a library, but understanding * the underlying structure is crucial for interviews and debugging. */ class MinHeap { private heap: number[] = []; get size(): number { return this.heap.length; } peek(): number | undefined { return this.heap[0]; } push(value: number): void { this.heap.push(value); this.bubbleUp(this.heap.length - 1); } pop(): number | undefined { if (this.heap.length === 0) return undefined; const min = this.heap[0]; const last = this.heap.pop()!; if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(0); } return min; } // Replace root with new value (more efficient than pop + push) replace(value: number): number { const min = this.heap[0]; this.heap[0] = value; this.bubbleDown(0); return min; } private bubbleUp(index: number): void { while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); if (this.heap[parentIndex] <= this.heap[index]) break; [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]]; index = parentIndex; } } private bubbleDown(index: number): void { const length = this.heap.length; while (true) { const leftChild = 2 * index + 1; const rightChild = 2 * index + 2; let smallest = index; if (leftChild < length && this.heap[leftChild] < this.heap[smallest]) { smallest = leftChild; } if (rightChild < length && this.heap[rightChild] < this.heap[smallest]) { smallest = rightChild; } if (smallest === index) break; [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]]; index = smallest; } } toArray(): number[] { return [...this.heap]; } } /** * Find the K largest elements using a min-heap. * * Time Complexity: O(n log K) * Space Complexity: O(K) */ function topKLargest(arr: number[], k: number): number[] { if (k <= 0) return []; if (k >= arr.length) return [...arr]; const minHeap = new MinHeap(); for (const element of arr) { if (minHeap.size < k) { // Phase 1: Fill the heap minHeap.push(element); } else if (element > minHeap.peek()!) { // Phase 2: Replace weakest candidate minHeap.replace(element); } } return minHeap.toArray(); } // Example usage const arr = [5, 2, 9, 1, 7, 6, 8]; console.log(`Array: ${arr}`); console.log(`Top 3 largest: ${topKLargest(arr, 3).sort((a, b) => b - a)}`); // Output: Top 3 largest: [9, 8, 7]7d:T71f,The basic Top-K pattern extends naturally to several common variations. Understanding these helps you recognize Top-K problems in different disguises. **Variation 1: Kth Largest Element (Single Element)** Sometimes you don't need all K elements—just the Kth one: ```python def kth_largest(arr, k): """The Kth largest is the root of the min-heap after processing.""" min_heap = [] for element in arr: heapq.heappush(min_heap, element) if len(min_heap) > k: heapq.heappop(min_heap) # Evict smallest return min_heap[0] # Root is Kth largest ``` The min-heap root IS the Kth largest—no additional work needed. **Variation 2: Top-K Frequent Elements** Instead of comparing by value, compare by frequency: ```python def top_k_frequent(arr, k): """Find K most frequently occurring elements.""" # Step 1: Count frequencies - O(n) freq = Counter(arr) # Step 2: Use min-heap on frequencies - O(m log K) where m = unique elements min_heap = [] # (frequency, element) for element, count in freq.items(): heapq.heappush(min_heap, (count, element)) if len(min_heap) > k: heapq.heappop(min_heap) return [element for _, element in min_heap] ``` **Variation 3: Top-K with Custom Comparator** Real-world objects have multiple attributes. Use a comparison key: ```python def top_k_products_by_rating(products, k): """Find K highest-rated products, breaking ties by price (lower wins).""" min_heap = [] # (rating, -price, product) - negate price for tie-breaking for product in products: key = (product.rating, -product.price, product) heapq.heappush(min_heap, key) if len(min_heap) > k: heapq.heappop(min_heap) return [item[2] for item in min_heap] ```72:{"json":{"id":"seed_218c2dcb4053779f26e6206e0a5dd00d","slug":"top-k-problems-and-heap-applications","category":"Data Structures & Algorithms","topic":"Top-K Problems & Heap Applications","title":"Top-K Problems & Heap Applications","description":"Master the Top-K pattern using heaps—one of the most practical and frequently tested algorithmic techniques. Learn space-efficient tracking, stream processing, and real-world applications from task scheduling to median maintenance.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_aa5716dee188a66da55a8749c96a6249","title":"Top-K Pattern with Heaps","order":0,"content":[{"id":"opening-hook","title":"The Ubiquitous Top-K Problem","content":[{"data":{"content":"Imagine you're building a recommendation system for an e-commerce platform with 100 million products. A user searches for \"wireless headphones,\" and your algorithm assigns a relevance score to each product. Now you need to display the **top 10 most relevant results**. How do you efficiently find these 10 products without sorting all 100 million items?\n\nOr consider a real-time analytics dashboard that monitors server performance across 10,000 machines. You need to identify the **5 servers with the highest CPU usage** to alert the operations team. The data changes every second—you can't afford to sort all 10,000 entries each time.\n\nThese are instances of the **Top-K problem**—one of the most ubiquitous patterns in software engineering. The naive approach (sort everything, take the first K) has O(n log n) time complexity. But with the right data structure—the heap—we can solve this in **O(n log K)** time, or even better in streaming scenarios."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the Top-K pattern at a deep level: why heaps are the optimal choice, when to use a min-heap versus a max-heap, the critical insight of maintaining a \"bounded window\" of K elements, and how to recognize Top-K problems in disguise. This pattern appears in coding interviews, system design, and production systems regularly.","variant":"info"},"type":"callout"}]},{"id":"defining-top-k-problem","title":"Defining the Top-K Problem","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Kth Element as Threshold","content":"A crucial insight: finding the \"Kth largest element\" is equivalent to finding the threshold that separates the Top-K from the rest. Once you have this threshold, you can identify all elements in the Top-K set with a single pass. This connection is fundamental to efficient Top-K algorithms.","variant":"tip"},"type":"callout"},{"data":{"content":"**Variants of the Top-K Problem:**"},"type":"text"},{"data":{"rows":[["**Top-K Largest**","Find K elements with highest values","Highest-rated products, top-earning employees"],["**Top-K Smallest**","Find K elements with lowest values","Nearest neighbors, minimum costs"],["**Top-K Frequent**","Find K most frequently occurring elements","Most common words, trending hashtags"],["**Kth Largest/Smallest**","Find the single element at position K","Median (K = n/2), percentile calculations"],["**Top-K in Streaming**","Maintain Top-K as new elements arrive","Real-time leaderboards, live monitoring"]],"headers":["Variant","Description","Example Use Case"]},"type":"table"},{"data":{"content":"Each variant uses the same fundamental heap-based approach, with slight modifications. Mastering the core pattern enables you to solve all variants."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"why-not-just-sort","title":"Why Not Just Sort?","content":[{"data":{"content":"The most intuitive approach to Top-K is simple: sort the collection, then take the first K elements. Let's analyze why this isn't optimal.\n\n**The Sorting Approach:**\n```\nfunction topKBySorting(arr, k):\n sort(arr) // O(n log n)\n return arr[0...k-1] // O(k)\n```\n\n**Time Complexity:** O(n log n) — dominated by the sorting step\n**Space Complexity:** O(1) to O(n) depending on sorting algorithm\n\n**The Problem:**\n\nThe sorting approach does far more work than necessary. Consider the search engine example with n = 100,000,000 products and K = 10:\n\n- **Sorting approach:** ~2.66 billion comparisons (n log n ≈ 100M × 26.6)\n- **What we actually need:** Information about just 10 elements\n\nWe're using a sledgehammer to hang a picture frame. Sorting computes the *complete ordering* of all elements when we only need the *partial ordering*—specifically, which elements are in the top K."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Wasted Work of Full Sorting","content":"When K is small relative to n, full sorting wastes effort determining the relative order of elements outside the Top-K. Whether element 1,000 ranks higher than element 2,000 is irrelevant if both are outside the Top-10. This is the key insight that motivates the heap-based approach.","variant":"warning"},"type":"callout"},{"data":{"content":"**Alternative Approaches and Their Trade-offs:**"},"type":"text"},{"data":{"rows":[["**Full Sort**","O(n log n)","O(1)–O(n)","Simple but inefficient for small K"],["**Partial Sort**","O(n log K)","O(K)","Some languages offer this; same as heap"],["**Heap-based**","O(n log K)","O(K)","Optimal for small K; works with streams"],["**QuickSelect**","O(n) average, O(n²) worst","O(1)","Faster average case but modifies input"],["**Median of Medians + QuickSelect**","O(n) guaranteed","O(1)","Optimal worst-case but complex"]],"headers":["Approach","Time Complexity","Space Complexity","Notes"]},"type":"table"},{"data":{"content":"For most practical scenarios, the **heap-based approach** provides the best balance:\n- O(n log K) time complexity\n- O(K) space complexity \n- Works on streams (elements arriving one at a time)\n- Simple to implement and understand\n- Consistent performance (no worst-case degradation)\n\nWhen K is very small (say, K ≤ 100) and n is very large, the heap approach is almost always the right choice."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"heap-based-solution","title":"The Heap-Based Solution — The Core Pattern","content":[{"data":{"content":"Now we arrive at the heart of the Top-K pattern. The heap-based approach is elegant, efficient, and widely applicable. Here's the key insight:\n\n> **To find the K largest elements, maintain a min-heap of size K. The smallest element in the heap is our \"admission threshold\"—any element larger must be in the Top-K.**\n\nWait—a *min-heap* for finding the *largest* elements? This counterintuitive choice is precisely what makes the algorithm efficient. Let's break it down step by step."},"type":"text"},{"data":{"icon":"Sparkles","title":"The Min-Heap Paradox","content":"Using a min-heap to find the maximum elements seems backwards, but it's the key insight. The min-heap lets us efficiently identify and evict the WEAKEST candidate from our Top-K set. We always know which element would be \"first to go\" if a better candidate arrives—it's right there at the top of the heap.","variant":"note"},"type":"callout"},{"data":{"content":"**The Algorithm:**\n\n```\nfunction topKLargest(arr, k):\n minHeap = new MinHeap()\n \n for each element in arr:\n if minHeap.size() < k:\n // Phase 1: Fill the heap until we have K elements\n minHeap.insert(element)\n else if element > minHeap.peek():\n // Phase 2: New element beats our weakest candidate\n minHeap.extractMin() // Remove weakest\n minHeap.insert(element) // Add new champion\n \n return minHeap.elements()\n```\n\n**Step-by-Step Trace:**\n\nLet's trace through finding the Top-3 from `[5, 2, 9, 1, 7, 6, 8]`:"},"type":"text"},{"data":{"rows":[["1","5","[5]","5","Insert (heap not full)"],["2","2","[2, 5]","2","Insert (heap not full)"],["3","9","[2, 5, 9]","2","Insert (heap now full with K=3)"],["4","1","[2, 5, 9]","2","Skip (1 ≤ 2, not a top candidate)"],["5","7","[5, 7, 9]","5","7 > 2 → Extract 2, Insert 7"],["6","6","[6, 7, 9]","6","6 > 5 → Extract 5, Insert 6"],["7","8","[7, 8, 9]","7","8 > 6 → Extract 6, Insert 8"]],"headers":["Step","Element","Heap Contents","Heap Min","Action"]},"type":"table"},{"data":{"content":"**Result:** [7, 8, 9] — the three largest elements."},"type":"text"},{"data":{"fileName":"top_k_largest.py","languages":[{"code":"$7b","label":"Python","value":"python"},{"code":"$7c","label":"TypeScript","value":"typescript"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"why-min-heap-for-maximum","title":"Why Min-Heap for Finding Maximum Elements?","content":[{"data":{"content":"This is the most common point of confusion for engineers learning the Top-K pattern. Let's build a deep, intuitive understanding of why the heap choice seems \"backwards.\"\n\n**The Insight: Gatekeeping, Not Championing**\n\nThink of the heap as a **waiting room with limited capacity K**. We want to keep the K strongest candidates inside.\n\nThe crucial question isn't \"Who's the strongest?\" but rather **\"Who should we kick out if someone better arrives?\"**\n\nFor this gatekeeping role, the heap root tells us:\n- In a **min-heap**: Who is the *weakest* current occupant? (First to be evicted)\n- In a **max-heap**: Who is the *strongest* current occupant? (Not useful for eviction)\n\nWhen finding K largest elements, we need quick access to the weakest candidate—the one we'll evict when a better candidate arrives. That's what the min-heap root provides."},"type":"text"},{"data":{"left":[{"data":{"items":["Root = smallest in Top-K (threshold)","Root is our 'weakest link'","New element > root? Evict root, admit new element","New element ≤ root? Reject—can't beat the weakest","O(1) to check if element qualifies","O(log K) to perform replacement"],"title":{"icon":"CheckCircle","text":"Min-Heap for K Largest","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Root = largest in Top-K (champion)","But we don't need to evict the champion!","To find who to evict, must scan entire heap","Eviction becomes O(K) instead of O(log K)","Total complexity degrades to O(nK)","Defeats the purpose of using a heap"],"title":{"icon":"XCircle","text":"Max-Heap for K Largest (Wrong)","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"The Golden Rule","content":"**For Top-K Largest → Use Min-Heap (quick access to weakest candidate)**\n**For Top-K Smallest → Use Max-Heap (quick access to strongest candidate)**\n\nThe heap type is OPPOSITE to what you're looking for because you need quick access to the element that would be EVICTED, not the element you want to keep.","variant":"tip"},"type":"callout"},{"data":{"content":"**Worked Example: Why Max-Heap Fails**\n\nSuppose we incorrectly use a max-heap to find the Top-3 largest from [5, 2, 9, 1, 7]:"},"type":"text"},{"data":{"rows":[["1","5","[5]","— (not full)"],["2","2","[5, 2]","— (not full)"],["3","9","[9, 5, 2]","— (now full)"],["4","1","[9, 5, 2]","Must scan all 3 to find min (2). O(K)"],["5","7","[9, 7, 5]","Must scan all 3 to find min (2), then restructure. O(K)"]],"headers":["Step","Element","Max-Heap","To find eviction candidate..."]},"type":"table"},{"data":{"content":"With a max-heap, every new element requires scanning the entire heap to find the minimum. For n elements, that's O(nK) total—worse than sorting when K is large!\n\nWith a min-heap, the minimum is always at the root—O(1) access, and O(log K) for the replacement. Total: O(n log K)."},"type":"text"}],"titleType":"number","titleNumber":4},{"id":"complexity-analysis","title":"Complexity Analysis — Understanding the Efficiency","content":[{"data":{"content":"Let's rigorously analyze the time and space complexity of the heap-based Top-K algorithm.\n\n**Time Complexity: O(n log K)**\n\nBreaking down the operations:\n\n1. **For each of n elements:**\n - Comparison with heap root: O(1)\n - If heap not full: Insert → O(log K)\n - If new element qualifies: Extract + Insert (or Replace) → O(log K)\n\n2. **Key insight: Heap size never exceeds K**\n - All heap operations are O(log K), not O(log n)\n - This is the source of efficiency when K << n\n\n3. **Worst case: Every element triggers insertion**\n - Happens when elements arrive in increasing order\n - Still O(n log K) because each insertion is O(log K)\n\n4. **Best case: After initial K elements, no replacements**\n - Happens when K largest elements come first\n - O(K log K) for initial build + O(n - K) for comparisons\n - Effectively O(n) when K << n"},"type":"text"},{"data":{"rows":[["Full Sort","O(n log n)","~2.66 billion ops","Wasteful for small K"],["Heap-Based","O(n log K)","~332 million ops","8x faster for this example"],["QuickSelect","O(n) average","~100 million ops","Fastest average, but worst case O(n²)"],["Median of Medians","O(n) guaranteed","~500 million ops","Larger constants, complex implementation"]],"caption":"Time Complexity Comparison for Top-K","headers":["Approach","Time Complexity","When n=10⁸, K=10","Notes"]},"type":"table"},{"data":{"content":"**Space Complexity: O(K)**\n\nThe heap maintains exactly K elements at any time. This is crucial for:\n- **Memory-constrained environments**: Can process billions of elements with tiny heap\n- **Stream processing**: Never need to store the full input\n- **Distributed systems**: Each node keeps local Top-K, merge at the end\n\n**Concrete Example:**\n- n = 1 billion elements (need ~8GB to store all)\n- K = 100 (need ~800 bytes for heap)\n- Memory reduction: 10,000,000x!\n\nThis space efficiency is what enables stream processing of massive datasets."},"type":"text"},{"data":{"icon":"Zap","title":"The Power of Bounded Space","content":"The O(K) space bound means you can find the Top-100 elements from an infinite stream using constant memory. This is impossible with sorting approaches that require storing all elements. This property makes heaps indispensable for real-time analytics and streaming systems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"variations-extensions","title":"Variations and Extensions","content":[{"data":{"content":"$7d"},"type":"text"},{"data":{"icon":"Info","title":"Sorted Output Requirement","content":"If the problem requires the Top-K elements in sorted order, add a final O(K log K) sorting step. The heap gives you the K elements but not in sorted order. For K = 10, this adds negligible overhead. For larger K, consider whether sorted output is truly necessary.","variant":"note"},"type":"callout"},{"data":{"content":"**Variation 4: Top-K by Key/Score**\n\nVery common in recommendation systems and search engines:\n\n```python\ndef top_k_by_score(items: List[Tuple[str, float]], k: int) -> List[str]:\n \"\"\"\n Given items with scores, return K items with highest scores.\n \n items: List of (item_id, score) tuples\n Returns: List of item_ids for Top-K items\n \"\"\"\n min_heap = [] # (score, item_id)\n \n for item_id, score in items:\n if len(min_heap) < k:\n heapq.heappush(min_heap, (score, item_id))\n elif score > min_heap[0][0]:\n heapq.heapreplace(min_heap, (score, item_id))\n \n # Return in descending score order\n return [item_id for _, item_id in sorted(min_heap, reverse=True)]\n```\n\nThis pattern appears in:\n- Search result ranking\n- Product recommendations \n- Feed personalization\n- Fraud score prioritization"},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"common-mistakes","title":"Common Mistakes and Pitfalls","content":[{"data":{"content":"The Top-K pattern is simple in concept but has several common implementation pitfalls. Being aware of these will save you debugging time."},"type":"text"},{"data":{"items":["**Wrong heap type:** Using max-heap for K largest (should be min-heap). Remember: heap type is OPPOSITE to what you're finding.","**Forgetting the K bound:** Not limiting heap size leads to O(n log n) complexity—same as sorting!","**Off-by-one in heap size:** Should evict when size > K, not when size >= K.","**Incorrect comparison:** For Top-K largest, new element must be STRICTLY greater than heap root to qualify.","**Forgetting edge cases:** K = 0, K >= n, empty input array.","**Tie-breaking issues:** When values are equal, order may matter. Define consistent tie-breaking rules.","**Modifying input:** Some implementations modify the input array. Document and handle appropriately.","**Heap pollution:** In languages with type erasure (Java), mixing types causes subtle bugs."],"title":{"icon":"AlertCircle","text":"Common Pitfalls to Avoid","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"fileName":"top_k_edge_cases.py","languages":[{"code":"def top_k_largest_robust(arr: List[int], k: int) -> List[int]:\n \"\"\"\n Robust Top-K implementation handling all edge cases.\n \"\"\"\n # Edge case 1: Invalid K\n if k <= 0:\n return []\n \n # Edge case 2: K >= n (return all elements)\n if k >= len(arr):\n return list(arr) # Return copy, not reference\n \n # Edge case 3: Empty array\n if not arr:\n return []\n \n min_heap = []\n \n for element in arr:\n if len(min_heap) < k:\n heapq.heappush(min_heap, element)\n elif element > min_heap[0]: # STRICTLY greater\n heapq.heapreplace(min_heap, element)\n \n return min_heap\n\n\n# Test edge cases\nassert top_k_largest_robust([], 5) == []\nassert top_k_largest_robust([1, 2, 3], 0) == []\nassert top_k_largest_robust([1, 2, 3], 5) == [1, 2, 3]\nassert top_k_largest_robust([1, 1, 1], 2) == [1, 1] # Duplicates OK\nprint(\"All edge cases passed!\")","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The Top-K Pattern","content":[{"data":{"content":"We've explored the Top-K pattern in depth—one of the most practical applications of the heap data structure. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**The Top-K problem is ubiquitous**—finding K largest/smallest elements appears in search, recommendations, analytics, and countless other systems.","**Full sorting is wasteful** when K << n. Why compute the complete ordering when you only need K elements?","**Use a min-heap for Top-K largest** (and max-heap for smallest). The heap gives O(1) access to the eviction candidate.","**Time complexity is O(n log K)**, which is a significant improvement over O(n log n) sorting when K is small.","**Space complexity is O(K)**—enabling processing of massive streams with bounded memory.","**The pattern extends naturally** to Kth element, Top-K frequent, and custom comparators.","**Watch for common pitfalls**: wrong heap type, missing bound enforcement, and edge cases."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nIn the next page, we'll explore **space-efficient K element tracking**—how to maintain a Top-K set that can be dynamically updated as elements are added or removed, and techniques for reducing memory overhead even further."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Pattern Mastered","content":"You now understand the core Top-K pattern with heaps. This single pattern solves a wide variety of interview problems and real-world engineering challenges. In the upcoming pages, we'll build on this foundation to tackle more advanced scenarios including streaming data and real-world applications.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_171c22c90d30b054d6f2cd383305cb46","title":"Space-Efficient K Element Tracking","order":1,"content":null,"isLocked":true},{"id":"seed_3df052493ce09444cb0b3cfd127d96a1","title":"Stream Processing with Heaps","order":2,"content":null,"isLocked":true},{"id":"seed_c17876cf27520936b0b99c920c6ddef1","title":"Real-World Applications","order":3,"content":null,"isLocked":true}]}}