leetExpert

Module 19 · Heaps

Practice

Practice~2 min

How to practice this module

Heap drills reward keeping the right shape in O(log n): a size-k heap holds top-k, two heaps hold a running median, a heap of list heads merges k lists, and task scheduling re-pushes cooldowns. Done when all six show Solved in the hub.

Problems

Heaps — work them in order; difficulty ascends.

0/6

solved

  1. 1Kth Largest Element in a StreamEasySize-k min-heapWatch for: Emit the root after each add; only push values larger than the current kth-largest or the heap overgrows
  2. 2Top K Frequent ElementsMediumCount + size-k heapWatch for: Build the frequency map first, then a min-heap of size k keyed by frequency — the comparator is the frequency, not the value
  3. 3K Closest Points to OriginMediumMax-heap of size kWatch for: Closest points need a MAX-heap of size k that evicts the farthest; compare by squared distance
  4. 4Merge k Sorted ListsHardHeap of list headsWatch for: Push each head with its list identity; after popping, push that same list's next node
  5. 5Find Median from Data StreamHardTwo-heap medianWatch for: Max-heap holds the lower half, min-heap the upper; rebalance so the sizes differ by at most one
  6. 6Task SchedulerMediumGreedy with heap + cooldownWatch for: Run the most frequent eligible task; park just-run tasks in a cooldown queue and re-push them when their gap clears

Cheatsheet

Heaps — Priority in O(log n) — top-K and running medians live here.

Smell → pattern

  • Repeated extract-min/maxBinary heap
  • Top K in a streamSize-K heap
  • Merge K sortedHeap of heads
  • Cooldown / gap schedulingGreedy with heap

Patterns

Size-K heap

Core

Smell: Top K of a stream / array

For top K largest, keep a min-heap of size K. Evict the smallest when over capacity — heap root is the threshold.

min

Two-heap median

Safe

Smell: Running median as values arrive

Max-heap for the lower half, min-heap for the upper. Rebalance sizes so the median sits at the boundary.

min

K-way merge

Reach

Smell: Merge K sorted lists / arrays

Push the next item from each list with its list id. Pop global min, push that list’s successor.

write region

Greedy with heap (cooldown)

Careful

Smell: Task scheduler / spaced gaps

Always run the task with the largest remaining count; park just-run tasks in a cooldown queue until their gap clears. A plain queue drifts from optimal.

min

Complexity targets

  • Push / pop

    Time
    O(log n)
    Space
    O(n)
    Note
    n = heap size

  • Top-K over stream

    Time
    O(n log k)
    Space
    O(k)
    Note
    Better than full sort

  • K-way merge

    Time
    O(n log k)
    Space
    O(k)
    Note
    n total items, k lists

Traps

  • Min vs max heap mix-up

    Top-K largest needs a min-heap of size K (evict small). Flipping the heap type silently inverts the answer.

  • Comparing tuples incorrectly

    When the heap stores (value, index, …), define the full comparison. Partial compares break ties and corrupt order.

  • Cooldown queue vs heap state

    A task on cooldown must re-enter the heap, not stay parked. Forgetting to re-push is how task-scheduler counts come out too small.