// Heap & Top-K

core idea

PriorityQueue<TElement, TPriority> buys you one cheap operation — always know the smallest live element in O(1), maintained at O(log n) per insert/remove — and the entire top-K family is built on top of that one operation. Instead of fully sorting O(n log n) worth of data, you keep a heap capped at exactly the size you need, so every push and pop only pays for what you’re tracking, never for everything you’ve seen. Three shapes cover the family:

when to reach for it

• “Kth largest/smallest”, “top K”, “K closest” in the prompt — you never need full order, just the boundary.
• Several already-sorted sources need combining — a heap always knows which source’s next value is smallest, in O(log k) instead of a linear scan.
• The data keeps arriving (a stream) and you need a running statistic — the Kth largest so far, or the median so far — after every insertion.
• A comparison-based structure is genuinely needed. If values have a small bounded range, bucket or counting sort (see Sorting for Interviews) beats a heap outright.

universal templates

Bounded min-heap of size K — the shape you’ll write most often:

public int[] TopK(int[] nums, int k)
{
    var heap = new PriorityQueue<int, int>();     // min-heap: root is the smallest kept

    foreach (var n in nums)
    {
        heap.Enqueue(n, n);
        if (heap.Count > k) heap.Dequeue();        // evict the smallest — it can't be in the top K
    }
    return [.. heap.UnorderedItems.Select(x => x.Element)];
}

K-way merge — one heap slot per source, refilled the instant it’s consumed:

public int[] KWayMerge(int[][] sortedSources)
{
    // (value, which source, index within that source)
    var heap = new PriorityQueue<(int Value, int Src, int Idx), int>();
    for (int s = 0; s < sortedSources.Length; s++)
        if (sortedSources[s].Length > 0)
            heap.Enqueue((sortedSources[s][0], s, 0), sortedSources[s][0]);

    var result = new List<int>();
    while (heap.TryDequeue(out var top, out _))
    {
        result.Add(top.Value);                     // top is the smallest live candidate — safe to emit
        int nextIdx = top.Idx + 1;
        if (nextIdx < sortedSources[top.Src].Length)
            heap.Enqueue((sortedSources[top.Src][nextIdx], top.Src, nextIdx), sortedSources[top.Src][nextIdx]);
    }
    return [.. result];
}

Two heaps, balanced around the middle:

public class TwoHeapMedian
{
    private readonly PriorityQueue<int, int> _lo = new(Comparer<int>.Create((a, b) => b.CompareTo(a))); // max-heap: lower half
    private readonly PriorityQueue<int, int> _hi = new();                                                // min-heap: upper half

    public void Add(int num)
    {
        _lo.Enqueue(num, num);
        _hi.Enqueue(_lo.Peek(), _lo.Peek());       // shuttle lo's current max into hi unconditionally...
        _lo.Dequeue();
        if (_hi.Count > _lo.Count)                 // ...then undo it if that left hi too big
        {
            _lo.Enqueue(_hi.Peek(), _hi.Peek());
            _hi.Dequeue();
        }
    }

    public double Median() =>
        _lo.Count > _hi.Count ? _lo.Peek() : (_lo.Peek() + _hi.Peek()) / 2.0;
}

Every problem below is one of these three skeletons with a different priority key or comparer.

problems

Five problems across the three shapes above — the first three are all the bounded heap (stream, batch, and derived-key), then one K-way merge and one two-heap problem:

1. 01Kth Largest Element in a StreameasyLC #703

   The size-K min-heap idea in its purest form.

2. 02Kth Largest Element in an ArraymediumLC #215

   Min-heap of size K — with the quickselect and K-Closest-Points variants.

3. 03Top K Frequent ElementsmediumLC #347

   Frequency map + heap of size K; bucket sort gets O(n).

4. 04Merge K Sorted ListshardLC #23stretch

   The heap always knows which of K heads is smallest.

5. 05Find Median from Data StreamhardLC #295stretch

   Two heaps balanced around the middle — the two-heaps sub-pattern.