Top-K Elements

What you'll learn

• The Golden Rule

  Whenever you are asked for the top K, bottom K, or most frequent K elements from a collection, use a heap of size K. This single insight solves an entire family of problems. The heap acts as a sliding window that maintains only the K ele…

• Why a Min-Heap of Size K for "K Largest"?

  This is the counterintuitive insight that trips people up: to find the K largest elements, you use a min-heap. Here is why: The min-heap's root is always the smallest among the K largest seen so far. It acts as a gatekeeper: only element…

• Three Approaches Compared

  | Approach | Time | Space | Best When | |----------|------|-------|-----------| | Sort entire array | O(n log n) | O(n) | You need all elements in order | | Heap of size K | O(n log k) | O(k) | K is much smaller than n | | QuickSelect |…

• Pattern 2: Kth Largest Element

  A special case: you only need the single Kth largest element. Key insight: After building a min-heap of size K, the root IS the Kth largest element. Why does this work? The heap contains exactly K elements, all larger than or equal to th…

• Pattern 3: K Most Frequent Elements

  Two-step approach: First count frequencies, then find top-K frequencies using a heap.

• Pattern 4: K Closest Points to Origin

  Use a max-heap of size K (or min-heap with negated distances). Why max-heap? We want the K smallest distances. The max-heap's root is the largest distance among our K candidates — acting as a gatekeeper that rejects points farther than o…

• Pattern 5: Sort Characters by Frequency

  Build a frequency map, then use a max-heap to extract characters from most to least frequent.

• Pattern 6: Reorganize String (No Adjacent Same Characters)

  This is the most complex top-K variant. Use a max-heap with a cooldown mechanism. Strategy: Always place the most frequent character next, but track the previously placed character so it cannot be placed again immediately.

• When to Use QuickSelect Instead

  QuickSelect finds the Kth smallest/largest element in O(n) average time without maintaining a heap. Choose QuickSelect when: - You only need the Kth element (not all K elements) - Data is in memory (not streaming) - Average-case performa…

• Summary Decision Framework

• Key Takeaways

  1. Min-heap of size K for K largest — the root is your gatekeeper 2. Max-heap of size K for K smallest — same logic, inverted 3. Frequency map + heap for most-frequent problems 4. Negate values in Python to simulate a max-heap 5. Heap si…