λDSA Learning Hubpart of DSA Atlas

Heaps & Priority Queues

Intermediate~3h · 8 lessons10 practice problems

Complete trees in arrays with parents ≤ children: O(1) minimum, O(log n) push/pop, O(n) heapify — and the top-k / k-way-merge / running-median patterns.

0 of 8 lessons checked off

Introduction

What it is

  • A binary heap is a COMPLETE binary tree (levels fill left to right) obeying one local rule: in a min-heap every parent ≤ its children. The global consequence: the minimum sits at the root.
  • Completeness means no pointers are needed — the tree lives in an array where node i's children are at 2i+1 and 2i+2 and its parent at (i−1)//2.

Why it matters

  • A heap is the answer to 'I repeatedly need the smallest/largest thing': O(1) peek, O(log n) insert and extract — the engine of priority queues.
  • It powers a pattern family interviews adore: top-k elements, k-th largest, merge k sorted lists, running median, task scheduling by deadline.

How it works

  • Insert: append at the end (keeping completeness), then sift UP while smaller than the parent.
  • Extract-min: take the root, move the LAST element to the root, sift DOWN swapping with the smaller child.
  • Heapify an entire array bottom-up in O(n) — cheaper than n pushes (O(n log n)), a favourite complexity question.

Where it's used

  • OS schedulers pick the next task by priority; Dijkstra pops the closest node; timers fire the soonest deadline; load balancers pop the least-loaded server. Python's heapq is a min-heap over a plain list.

In interviews

  • Kth largest element, top-k frequent, merge k sorted lists, median from a data stream (two heaps), meeting rooms II, task scheduler.
Analogy: An emergency room: patients (values) arrive in any order, but the desk always knows who's most critical (the root). Discharging them promotes the next-most-critical in a few comparisons — nobody re-sorts the whole waiting room.

Interactive diagram

The new value enters at the only shape-legal slot, then swaps upward until its parent is smaller.

1297853
Min-heap before insert

Array form: [3, 7, 5, 12, 9, 8]. Parent of index i lives at (i − 1) // 2 — no pointers needed.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Heap property and array representation

    Complete shape → index arithmetic instead of pointers.

    20 min
  2. Insert and sift-up

    Append, then bubble toward the root while violating.

    20 min
  3. Extract and sift-down

    Last element to root, swap with the SMALLER child.

    20 min
  4. Heapify in O(n)

    Bottom-up sift-downs and why the sum telescopes to O(n).

    20 min
  5. Python's heapq (and max-heap tricks)

    Negation, (priority, item) tuples, tie-breaking.

    15 min
  6. Top-k and k-th largest

    A size-k min-heap of the best-so-far: O(n log k).

    25 min
  7. Merge k sorted lists

    A k-sized heap of list heads: O(N log k).

    20 min
  8. Median from a data stream

    Max-heap of the low half + min-heap of the high half.

    20 min

Operations

Insert (sift-up)

Append at the array end — completeness preserved — then repair the ordering upward: at most one swap per level.

1297853
Min-heap before insert

Array form: [3, 7, 5, 12, 9, 8]. Parent of index i lives at (i − 1) // 2 — no pointers needed.

def heap_push(heap: list[int], value: int) -> None:    """Min-heap insert. O(log n)."""    heap.append(value)                    # only legal slot (completeness)    i = len(heap) - 1    while i > 0:        parent = (i - 1) // 2        if heap[parent] <= heap[i]:       # order restored            break        heap[parent], heap[i] = heap[i], heap[parent]        i = parent
Time: O(log n) worst, O(1) average for random valuesSpace: O(1)

Edge cases

  • Empty heap: the value becomes the root, loop never runs.
  • Value equal to parent: stop (≤, not <) — needless swaps waste time and can break tie stability expectations.
  • New global minimum bubbles all the way to index 0.

Common mistakes

  • Inserting at the root and sifting down (breaks completeness).
  • Wrong parent formula — it's (i − 1) // 2, not i // 2.

Extract-min (sift-down)

Root out, last element in, then swap downward with the SMALLER child until both children are larger.

12938752
Pop the minimum

The root (2) is the answer — a min-heap always keeps its smallest value at index 0.

def heap_pop(heap: list[int]) -> int:    """Remove and return the minimum. O(log n)."""    if not heap:        raise IndexError("pop from empty heap")    minimum = heap[0]    last = heap.pop()    if heap:        heap[0] = last                    # fill the hole, then repair down        i, n = 0, len(heap)        while True:            left, right = 2 * i + 1, 2 * i + 2            smallest = i            if left < n and heap[left] < heap[smallest]:                smallest = left            if right < n and heap[right] < heap[smallest]:                smallest = right            if smallest == i:                break            heap[i], heap[smallest] = heap[smallest], heap[i]            i = smallest    return minimum
Time: O(log n)Space: O(1)

Edge cases

  • Single element: pop it, no sift needed.
  • A node with only a left child (last internal node) — the right-bound checks matter.
  • Popping empty must raise.

Common mistakes

  • Swapping with ANY smaller child instead of the SMALLEST — the promoted value can still exceed the other child.
  • Forgetting the heap-emptied case after pop().

Top-k pattern (size-k heap)

Keep a min-heap of the k best seen so far; anything beating the heap's minimum replaces it. n items, log k work each.

Top-k pattern (size-k heap)
import heapqdef k_largest(nums: list[int], k: int) -> list[int]:    """k largest values. O(n log k) time, O(k) space."""    heap: list[int] = []    for x in nums:        if len(heap) < k:            heapq.heappush(heap, x)        elif x > heap[0]:                 # beats the weakest of the best            heapq.heapreplace(heap, x)    # pop+push in one O(log k)    return sorted(heap, reverse=True)def kth_largest(nums: list[int], k: int) -> int:    return k_largest(nums, k)[-1]
Time: O(n log k) — beats full-sort O(n log n) when k ≪ nSpace: O(k)

Edge cases

  • k ≥ n: everything qualifies.
  • Duplicates: x > heap[0] keeps equal values out; use >= if ties should replace.
  • Streaming input: the same loop works online — the heap IS the state.

Common mistakes

  • Using a max-heap of ALL n items (O(n) space) when O(k) was the point.
  • Min/max confusion: k LARGEST needs a MIN-heap of candidates.

Complexity analysis

OperationBestAverageWorstSpace
peek min/maxO(1)O(1)O(1)—
push / popO(1)O(log n)O(log n)O(1)
heapify n itemsO(n)O(n)O(n)O(1)
search arbitrary valueO(1)O(n)O(n)—
heap sortO(n log n)O(n log n)O(n log n)O(1)

The search row is the trade-off: heaps order only along root-to-leaf paths. Need arbitrary lookup too? Pair the heap with a hash map (or use a BST).

Python implementation

Production-quality code with type hints, validation, and docstrings.

Median from a data stream (the two-heap design)
import heapqclass MedianFinder:    """Running median: max-heap of the low half, min-heap of the high half.    add: O(log n) · median: O(1)."""    def __init__(self) -> None:        self._low: list[int] = []    # max-heap via negation        self._high: list[int] = []   # min-heap    def add(self, num: int) -> None:        # 1. route: everything ≤ low's max goes low        if self._low and num > -self._low[0]:            heapq.heappush(self._high, num)        else:            heapq.heappush(self._low, -num)

What interviewers expect you to know

What interviewers expect you to know

  • Array indexing: children 2i+1 / 2i+2, parent (i−1)//2 — no pointer version exists in practice.
  • Heapify is O(n), not O(n log n): most nodes are near the leaves and sift almost nowhere; the level sums telescope.
  • heapq is min-only: negate for max-heaps, or push (priority, tiebreak, item) tuples.
  • A heap is NOT a sorted array: only root-to-leaf paths are ordered; the array read left-to-right is not sorted.

Pattern triggers

  • 'k largest / smallest / most frequent / closest' → size-k heap, O(n log k).
  • 'merge k sorted …' → heap of k heads, O(N log k).
  • 'running median / percentile' → two heaps.
  • 'schedule by earliest deadline / smallest end time' → heap inside a greedy (meeting rooms II).

Follow-ups to expect

  • "Why is heapify O(n)?" — sift-down cost is the node's height; Σ n/2^(h+1) · h = O(n).
  • "Heap vs BST?" — heap: cheaper, cache-friendly, min-only; BST: full ordering, arbitrary search, successor queries.
  • "Decrease-key?" — heapq lacks it; standard workaround is lazy deletion (push the new entry, skip stale ones on pop) — the Dijkstra idiom.

Common mistakes

Treating the heap array as sorted

Only parent-child pairs are ordered. heap[1] is NOT the second smallest necessarily — pop twice if you need the second smallest.

Sifting down with the wrong child

Swap with the SMALLER child (min-heap). Swapping with the larger leaves a violation behind.

O(n log n) heapify

Pushing n items one by one is O(n log n); bottom-up heapify is O(n). Saying the first when asked for the second costs points.

Max-heap improvisation errors

Negate on push AND on read. Mixed sign conventions produce silently wrong answers.

Unstable tuple comparisons

Pushing (priority, object) crashes when priorities tie and objects aren't comparable. Add a counter: (priority, seq, object).

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (1)

Medium (6)

Hard (3)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. In the array min-heap [2, 5, 3, 9, 6, 4], what are the children of the value 5?
  2. Complexity2. Building a heap from n unsorted items with bottom-up heapify costs…
  3. Scenario3. Find the 10 largest of 10 million streaming values in O(10) memory-ish. Which tool?
  4. Concept4. Why does the running-median design use a MAX-heap for the lower half?
  5. Concept5. Which requirement should make you abandon a heap for another structure?
0 of 5 answered

Frequently asked questions

How do I get a max-heap in Python?

Negate: push -x, read -heap[0]. For objects, push (-priority, seq, item) with an incrementing seq to break ties. (heapq._heapify_max exists but is private — don't rely on it.)

Heap sort vs quicksort/mergesort — when would I pick it?

Heap sort gives guaranteed O(n log n) AND O(1) extra space — the only mainstream sort with both. It loses on constants and cache behaviour, so in practice it's a fallback (introsort switches to it when quicksort recursion gets deep).

When do I need a d-ary or Fibonacci heap?

Interview answer: almost never — name-drop only. d-ary heaps trade cheaper sift-down for costlier sift-up (good when pushes dominate); Fibonacci heaps improve Dijkstra's theoretical bound with amortised O(1) decrease-key but lose in practice.

Summary & cheat sheet

Key takeaways

  • Complete shape + parent ≤ children: min at root, tree in an array.
  • push/pop O(log n); peek O(1); heapify O(n).
  • Top-k = size-k min-heap; k-way merge = heap of heads; running median = two heaps.
  • heapq is min-only — negate for max.
  • Heaps sacrifice arbitrary search; pair with a map when you need both.

Formulas & cheat sheet

  • children(i) = 2i+1, 2i+2 · parent(i) = (i−1)//2
  • heapify: Σ (n / 2^(h+1)) · h = O(n)
  • top-k: O(n log k) · k-way merge: O(N log k)

Interview checklist

  • I can implement sift-up and sift-down from memory.
  • I can explain O(n) heapify with the telescoping sum.
  • I can code kth-largest with a size-k heap and state why min-heap.
  • I can sketch the two-heap median design.