Heaps and Priority Queues

1. What It Is and Why It Exists

A binary heap is a complete binary tree (stored compactly in an array) maintaining the heap property: in a min-heap every parent is ≤ its children, so the minimum is always at the root. A priority queue is the abstract "always give me the most extreme element next" structure; a heap is its standard O(log n) implementation. It exists because many problems need repeated access to the current min/max of a changing set: keeping the data fully sorted costs O(n log n) and re-sorting on every change is wasteful, while a heap gives you the extreme in O(1) and insert/extract in O(log n).

The "why it works" intuition: a heap maintains only a partial order — just "parent beats child" — which is all you need when you only ever want the extreme, not a full sort. That weaker invariant is exactly why push/pop are O(log n) (one root-to-leaf sift) instead of O(n). The classic interview leverage: top-K, k-way merge, running median, and Dijkstra all reduce to "repeatedly pull the smallest/largest from a live set."

2. Operations and Complexity

Space O(n). Most-probed: heapify is O(n), not O(n log n) (bottom-up sift; the proof is a converging series — state the result, not the proof); a heap gives the extreme in O(1) but arbitrary search is O(n) (it is only partially ordered); heapq is min-heap only — for a max-heap push negatives (or (-key, item) tuples).

3. Implementation

A binary min-heap on an array, with the two sift routines that define it:

Copy
class MinHeap:
    def __init__(self):
        self._h = []                      # complete tree as array: kids of i are 2i+1, 2i+2

    def push(self, x):                    # O(log n): place at end, sift up
        self._h.append(x)
        i = len(self._h) - 1
        while i > 0 and self._h[(i - 1) // 2] > self._h[i]:
            par = (i - 1) // 2
            self._h[i], self._h[par] = self._h[par], self._h[i]
            i = par

    def pop(self):                        # O(log n): root is the min
        last = self._h.pop()
        if not self._h:
            return last
        top, self._h[0] = self._h[0], last
        i, n = 0, len(self._h)
        while True:                       # sift down to the smaller child
            l, r, smallest = 2*i + 1, 2*i + 2, i
            if l < n and self._h[l] < self._h[smallest]: smallest = l
            if r < n and self._h[r] < self._h[smallest]: smallest = r
            if smallest == i:
                break
            self._h[i], self._h[smallest] = self._h[smallest], self._h[i]
            i = smallest
        return top

In a real interview, use heapq on a plain list — never hand-roll the above unless asked:

Copy
import heapq
h = []
heapq.heappush(h, 3); heapq.heappush(h, 1)
heapq.heappop(h)                 # -> 1   (smallest)
heapq.heapify(arr)               # O(n) build in place
heapq.nlargest(k, arr)           # top-K convenience
# Max-heap: push -x and negate on pop, or push (-priority, item) tuples.

4. When to Reach for It

• "Top K", "K largest/smallest", "K closest" → a heap of size k: O(n log k) instead of O(n log n) from sorting.
• "K-th largest/smallest" in a stream or static array → size-k heap.
• Merge K sorted lists/streams → push one element per list, pop-and-refill (O(N log k)).
• "Running / sliding median" → two heaps (max-heap of low half, min-heap of high half).
• Dijkstra / Prim → priority queue keyed by current best distance/weight.
• Schedule by priority / repeatedly take the current extreme of a changing set.

5. Common Pitfalls

• Wanting a max-heap with heapq: it's min-only. Negate values, or push (-key, item) tuples — and remember to negate back on pop.
• Tuple ties throwing TypeError: (priority, item) comparison falls through to item when priorities tie; if item isn't orderable it crashes. Add a tie-breaker: (priority, counter, item).
• Thinking heapify is O(n log n): bottom-up build is O(n). Stating it wrong is a classic miss.
• Searching/deleting an arbitrary element: that's O(n) — a heap isn't sorted. Use lazy deletion (mark stale, skip on pop) or an index map.
• Heap vs sorted: a heap gives you the extreme cheaply but iterating it in order still costs O(n log n) — it is not a sorted container.
• Wrong-size top-K heap: for the k largest, keep a min-heap of size k (pop the smallest when it exceeds k) — using a max-heap of all n defeats the point.

6. Interview Cheat Sheet

• "A heap keeps only a partial order — parent beats child — so I get the extreme in O(1) and push/pop in O(log n); full sort isn't needed."
• "heapify builds in O(n) bottom-up, not O(n log n)."
• "For top-K I keep a size-k min-heap → O(n log k), better than sorting's O(n log n)."
• "heapq is min-only; for a max-heap I push negatives or (-key, item) tuples, with a counter tie-breaker to avoid comparing unorderable items."

Follow-ups:

• "Top K vs sorting?" — Heap of size k: O(n log k) time, O(k) space; sorting is O(n log n). Quickselect can get the kth element in O(n) average but doesn't keep them ordered.
• "Find the running median." — Two heaps: a max-heap for the lower half and a min-heap for the upper half, rebalanced so sizes differ by ≤1; median is a root (or the average of both roots). O(log n) per insert.
• "Decrease-key for Dijkstra?" — heapq has no decrease-key; push the updated (dist, node) and skip stale pairs when popped (lazy deletion) — overall still O(E log V).