Heap / Priority Queue

Reach for it when

• Top K / K-th largest / K closest
• Merge K sorted streams
• Repeatedly process the cheapest or earliest item (scheduling)

Core idea

A heap keeps the minimum at the root with O(log n) push and pop. For top-K largest, keep a min-heap of size K: the root is the weakest member and is evicted when something better arrives. Two heaps (max-heap low half, min-heap high half) maintain a running median.

Template · O(n log k) time, O(k) space

import heapq

def k_largest(nums, k):
    heap = []                       # min-heap of the k best
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # evict the weakest
    return heap[0]                  # k-th largest

int kthLargest(const vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;  // min-heap of the k best
    for (int x : nums) {
        heap.push(x);
        if ((int)heap.size() > k) heap.pop();             // evict the weakest
    }
    return heap.top();
}

Common pitfalls

• Python heapq is a min-heap: negate values for a max-heap
• Push tuples (priority, tiebreak, item) when items are not comparable

Practice · 0 / 8 done

• Kth Largest Element In a StreamEasy
• Last Stone WeightEasy
• Design TwitterMedium
• K Closest Points to OriginMedium
• Kth Largest Element In An ArrayMedium
• Reorganize StringMedium
• Task SchedulerMedium
• Find Median From Data StreamHard