Heaps & Priority Queues

Review boundary and corrected contracts

Bottom-up heapify is linear because most nodes have small height. Median query is O(1), insertion O(log n); frequency counting adds O(distinct) storage to a bounded heap. Python 3.14 adds max-heap functions, while negation remains portable. Dijkstra requires nonnegative weights.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Use Python's heapq fluently for top-K, streaming median, event scheduling, and the canonical Dijkstra loop — and know when a heap beats sorting.

Why this session exists

A heap is a partially-sorted tree that gives you O(1) access to the smallest (or largest) element and O(log n) insert/pop. A priority queue is useful for Dijkstra, next-event scheduling and bounded top-K selection. That does not imply Kafka ordering, every scheduler or every top-K query is implemented with a heap; sorting and other indexes can also fit. If you learn ONE algorithmic tool from S023–S034, make it two: hashmap and heap. This is heap day.

You will be able to

• Explain a binary heap in one sentence — and why it lives in an array instead of a tree of nodes.

• Use heapq.heappush / heappop confidently, and simulate a max-heap with negated values.

• Solve top-K frequent, k-th largest, and streaming median from memory.

• Write Dijkstra's shortest-path with a min-heap in ~15 lines.

• Recognise ‘schedule the next event’ patterns as priority-queue problems.

Prerequisites

• S028 · Trees & BSTs — a heap IS a complete binary tree.
• S024 · Hashmaps — combined with heaps for top-K by key.
• S027 · Recursion — tree-height reasoning helps; heapify can be implemented iteratively and does not require recursion.

Pre-read · skim before the session (25 min total)

Further reading: Python heapq docs

Further reading: LeetCode · Heap / Priority Queue tag

Further reading: Binary Heap (Wikipedia)

Optional archived videos

These original resource pointers are retained as optional practice aids, not governing evidence for technical claims.

• Heap Data Structure in 4 Minutes — archived title/attribution; playback, duration and channel identity not independently verified in this review.
• Top K Frequent Elements · Neetcode — archived title/attribution; playback, duration and channel identity not independently verified in this review.
• Dijkstra's algorithm in 3 minutes — archived title/attribution; playback, duration and channel identity not independently verified in this review.

(a) Intuition · 5 min

A heap is a hospital triage queue

Real: Emergency room: patients arrive at random. The next person seen is always the most critical, regardless of arrival order. Adding a patient is O(log n) — nurse walks them through triage. Pulling the next patient is O(log n) — reorganise so the next-most-critical bubbles up. The queue doesn't need to be fully sorted — it just needs to always yield the highest priority next. That partial ordering is way cheaper to maintain than full sorting.

 
    A min-heap: every parent is ≤ both children. Root = the minimum. Insert = append to end + sift-up. Pop = take root, move last element to root, sift-down. Both operations O(log n) — the height of a complete tree.
    The killer trick: a heap is stored in an ARRAY, not a tree of nodes. Node at index i has children at 2i+1 and 2i+2. No per-node child pointers are required; a Python list is an array of object references, not packed inline numeric values. Locality and speed depend on representation and workload.
  

Heap vs sorted list vs BST

Why heap wins for ‘give me the next best thing’

• Sorted list — O(n) insert (shift). O(1) get_min. Great only if inserts are rare.

• Balanced BST — O(log n) insert and O(log n) minimum lookup by walking left, or O(1) peek with a cached minimum. More general ordered operations; implementation constants vary.

• Heap — O(log n) insert, O(log n) pop_min, O(1) peek_min. Arbitrary-key search requires O(n) scanning unless augmented with another index. Perfect fit for priority queues.

• Rule: if you always want ‘the best’ or ‘the worst’ and don't need to search by value, use a heap.

Python version and ties matter

Python 3.14 adds public max-heap APIs such as heapify_max, heappush_max and heappop_max. The labs use portable negation: push -x and negate on pop. For an opaque payload use (-priority, counter, payload) so tied priorities do not compare payloads. A unique increasing counter also provides FIFO order among ties; heap ordering by itself is not stable. Only use finite, consistently ordered priorities—NaN does not provide a usable total ordering.

Timeline — the rise of the heap

Binary heaps connect array layout, priority queues and heapsort. Fibonacci heaps are a different theoretical design with amortised O(1) decrease-key and Dijkstra's O(E + V log V) bound; Python heapq is not one. Python's official 2.3 release notes introduce heapq (not 1994), and 3.14 adds its public max-heap API. Scheduling and distributed selection are applications of the abstraction, not dated claims that every named product adopted the same implementation.

(b) Keep the next minimum at the root · 15 min

The triage analogy promises only the next item, not a complete ranking. To see how a heap maintains that weaker guarantee cheaply, connect its tree-shaped ordering rule to the array positions that insertion and removal actually change.

Heap as an array — the index arithmetic that avoids pointers

Read the tree level by level to recover the array below it. For example, index 1 holds 15 and its children at indices 3 and 4 hold 20 and 18. The edges describe relationships calculated from positions; they are not stored pointers.

Notice that 15 appears before 12 in the array: the heap is not sorted. Each parent is no larger than its children, which is enough to place the minimum at index 0. Updates need to repair that local invariant, not reorder every entry.

Sift-up (insert) — bubble the new element toward the root

Append at end of array

Desc: Preserves completeness: every level except possibly the last is full, and the last fills left to right.

Compare with parent

Desc: parent index = (i-1) // 2. If child < parent (min-heap), swap.

Repeat

Desc: Continue until parent <= child, or you reach the root.

Cost

Desc: At most log₂(n) swaps — height of the tree.

Sift-down (pop) — replace root with last, bubble down

Insertion can violate the relationship with a parent; removing the minimum creates the opposite problem. The last element fills the root to preserve the complete shape, then moves downward until its relationships with its children are valid.

Save the root value (this is what you return)

Desc: It's the min.

Move the last array element to index 0

Desc: Keeps the tree complete.

Compare with the smaller child

Desc: children = 2i+1, 2i+2. If smallest child < parent, swap.

Repeat downward

Desc: Continue until both children ≥ parent, or you're at a leaf.

Cost

Desc: O(log n) levels; a level can use multiple comparisons (choose a child, then compare with the parent). Handle the empty/singleton heap separately.

Top-K frequent: heap of size K beats sorting

Once push and pop preserve the minimum, the root can serve as a cutoff. Among K retained candidates, it identifies the weakest one to evict when a better candidate arrives; the comparison below focuses on that selection step.

For frequency ranking distinguish n input occurrences from u distinct values. Count first with a hash map: expected O(n) time and O(u) space under ordinary hashing assumptions. Then either:

• Sort all u (frequency, value) candidates: O(u log u) time plus O(u) candidate storage; sorted output is immediately available.
• Retain m=min(K,u) candidates in a heap: O(u log(m+2)) selection time, O(m+1) peak heap space (push precedes eviction) in addition to O(u) counts. Return order is heap order, not descending rank; sorting the retained results adds O(m log m).
• Quickselect a materialised candidate array: expected O(u) partition work under suitable pivot choice, O(u²) worst case for a poor pivot strategy; it mutates that array and does not sort the winners.

A size-K heap alone is sufficient for top-K fixed-score items in a stream, not exact frequency counts over arbitrarily many distinct keys. If counts change, stale scores must also be updated or replaced. No wall-clock speedup follows solely from the asymptotic comparison.

Dijkstra with a heap — the shape of the loop

For top-K, the root is the candidate to discard. For Dijkstra on non-negative edge weights, it is the tentative route to examine next: a smaller accumulated distance has higher priority. The heap operation stays the same even though the meaning of the key changes.

Dijkstra in five lines

Name: 1. Initialise

Desc: dist[start] = 0, dist[all others] = ∞. Push (0, start) onto heap.

Name: 2. Pop (d, u) from heap

Desc: The entry has minimum queued tentative distance; it can be obsolete, so check staleness before expanding it.

Name: 3. Skip if stale

Desc: If d > dist[u], we already found a shorter path — ignore.

Name: 4. Relax outgoing edges

Desc: For each neighbor v with edge weight w: if dist[u] + w < dist[v], update dist[v] and push (new_dist, v).

Name: 5. Repeat until heap empty

Desc: With nonnegative finite weights, dist contains the shortest distance to each reachable node; unreachable vertices are absent in this implementation.

Lazy deletion versus indexed decrease-key

Python heapq has no indexed decrease-key API. Push a new (better_distance, node) entry and skip the old one when it becomes stale. An indexed binary heap can instead support O(log V) decrease-key with a position map; other priority queues have different bounds. The lazy variant here can retain O(E) entries and takes O((V+E) log(E+2)) time, whereas an indexed binary heap retains O(V) entries with O((V+E) log(V+1)) time. On simple connected graphs these are often both written O(E log V), but their storage contracts are not identical.

Getting the next minimum reliably can make the heap feel sorted. Return to the array in the first diagram before accepting that intuition: its out-of-order siblings are precisely the freedom that keeps updates cheap.

Myth: "A heap is a sorted structure. The smallest is at the top, so the array must be roughly in order."

Truth: Heap order constrains parents and descendants, not siblings or separate branches. A binary heap also has a complete shape. The root is the global minimum in a min-heap, but the array is not a sorted ranking.

Why: Because heappop repeatedly gives you sorted output, so it feels like the sorting already happened. It didn't — each pop does O(log n) work to re-establish the invariant. That partial-order weakness is the whole point: comparison-sorting n arbitrary items costs O(n log n) in the worst case, maintaining "parent ≤ children" costs O(n) to build and O(log n) per update. You bought a cheaper structure by asking for a weaker guarantee.

Test: A deterministic heap that is not sorted, with both child edges checked:

import heapq
 
def is_min_heap(xs):
    return all(xs[(i - 1) // 2] <= xs[i] for i in range(1, len(xs)))
 
xs = [10, 15, 12, 20, 18, 25]
assert is_min_heap(xs) and xs != sorted(xs)
assert not is_min_heap([1, 2, 0])  # only the right-child edge violates the rule
heapq.heapify(xs)
assert is_min_heap(xs)
print([heapq.heappop(xs) for _ in range(len(xs))])

Checking only left children misses the counterexample [1, 2, 0]. Heap order constrains every ancestor/descendant pair transitively, while unrelated branches need not be sorted.

Question: Why does heapify build a heap in O(n), when inserting n elements one at a time costs O(n log n)? Both end with a valid heap over the same n items — where did the log go?

Premise: Sift-down at a node costs work proportional to that node's height — the distance to the bottom of the tree, not to the root.

Because: sift-down moves an element downward, and it can move at most as far as the leaves are below it

Premise: In a complete binary tree, about half the nodes are leaves with height 0, a quarter have height 1, an eighth have height 2, and so on.

Because: each level up halves the node count — that is what "binary" means

Premise: So total heapify work is the sum over heights h of (number of nodes at height h) × h, which is bounded by a constant multiple of n × Σ (h / 2^(h+1)), with rounding for incomplete levels.

Because: work per node is its height, and node counts decay geometrically with height

Premise: That series converges to a constant (it sums to 1), so the total is O(n), not O(n log n).

Because: a geometrically decaying weight beats a linearly growing cost; the tall, expensive nodes are exponentially rare

Premise: Repeated insertion has the opposite profile: each insert sifts up from a leaf, and most elements are inserted when the tree is already near full depth.

Because: sift-up cost is depth, and most nodes are deep — the many-cheap/few-expensive asymmetry runs the wrong way

Conclusion: Therefore bottom-up heapify is O(n) and n incremental inserts have an O(n log n) worst-case upper bound (increasing min-heap insertions can take O(n) total comparisons). The useful distinction is which nodes pay long sifts, because that decides whether the expensive nodes are the rare ones or the common ones. And note what this predicts: if all data are available, heapify provides a linear worst-case construction bound; constants and input order still affect measurements. And it explains why heapsort is O(n log n) overall despite the O(n) build — the n pops each cost O(log n), and that is where the log n comes from, not the construction.

Name: Tournament bracket, loosely enforced

Picture: Picture a tournament bracket where every match result is recorded, but nobody ranked the losers. You know the champion — top of the tree — and you know each winner beat the two players below them. You know nothing about how two eliminated players compare. When the champion leaves, you don't re-run the tournament. You promote the last player into the empty slot and let them lose their way back down, one match per level: O(log n). That single operation is the whole data structure.

• Element 0 is globally minimum; every parent-child relation is also constrained. Heap order is not a complete ranking of siblings or separate branches.

• Push and pop are O(log n); peek is O(1); build-from-array is O(n); arbitrary-key search is O(n) without an auxiliary index.

• Stored as a flat array without child pointers: children of i are 2i+1 and 2i+2, parent is (i-1)//2. Contiguous, cache-friendly.

• Python 3.14 has public max-heap APIs. Portable numeric code may negate priorities; use (-priority, counter, item) to avoid comparing opaque payloads and to preserve FIFO ties.

Trigger: Fire this model the moment you see: "top K" or "K largest/smallest" · a scheduler picking the next-due task · Dijkstra or A* · merging many sorted streams (log-structured merge, sorted run merge) · rate limiting by next-available time · any "always process the most urgent thing" queue.

Decision: You need the top K items out of a stream of N, where N is large. Sort everything, or maintain a size-K heap?

Name: Sort all N, take first K

Gain: trivially correct, one line, and gives you the full ranking if you later want K+1 or the median; sorting is extremely well optimised

Cost: in-memory full sorting materialises N items and costs O(N log N) worst-case comparisons. External sorting can process disk-backed runs with bounded RAM, at additional I/O cost; it cannot produce a final ranking before an arbitrary stream ends

Pick: N fits comfortably in memory and you may need more than just the top K — the actual threshold depends on item size and the memory budget

Name: Size-K min-heap over the stream

Gain: O(N log(K+2)) time and O(K+1) state for fixed-score items, including K=0; a bounded heap avoids materialising the entire stream

Cost: you get exactly the top K unordered-until-you-drain-them, and nothing else — no median, no rank of item K+1; and constant factors can make a full sort competitive for small inputs

Pick: N does not fit in memory, or N is far larger than K — the classic threshold being that K is a fixed small number while N grows

Name: Quickselect (partial selection)

Gain: expected O(N) partition work with suitable pivot selection — and partitions the top K through repeated in-place passes; it is not a single-pass stream algorithm

Cost: requires all N in memory, mutates the input, has an O(N²) worst case without careful pivoting, and is not incremental

Pick: all N is already in memory, K is a large fraction of N, and you will do this once — e.g. computing a percentile cutoff over a materialised batch

Verdict: For fixed item scores and a consistent tie order, any item excluded from a partition's local top-K already has K local competitors ahead of it. Therefore the global top-K can be selected from the union of local top-K candidates. This is not valid for per-key frequencies split across partitions: counts must be aggregated. For K=1, partition one with A:4, X:3 and partition two with B:4, X:3 drops X locally even though global X:6 wins. A full-size heap can still support other workloads, but a size-K selection heap is what bounds candidate memory.

(c) Hands-on · 25 min

Save as heaps.py. Zero deps beyond stdlib.

"""heaps.py — the interview canon for heaps + a mini Dijkstra.
 
Run:  python heaps.py
"""
from __future__ import annotations
import heapq
from collections import Counter
from typing import Any
 
 
# ------------------------------------------------------------------
# 1) Top-K frequent — min-heap of size K
# ------------------------------------------------------------------
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """Return min(k,u) values in heap order; ties retain larger integer values.
 
    k is a nonnegative integer; counts add O(u) storage.
    Expected O(n + u*log(min(k,u)+2)) time, O(u) total auxiliary space.
    """
    counts = Counter(nums)
    heap: list[tuple[int, int]] = []            # (freq, value); freq is the sort key
    for val, freq in counts.items():
        heapq.heappush(heap, (freq, val))
        if len(heap) > k:
            heapq.heappop(heap)                 # drop the least-frequent
    return [v for _, v in heap]
 
 
# ------------------------------------------------------------------
# 2) K-th largest — same pattern, single number out
# ------------------------------------------------------------------
def kth_largest(nums: list[int], k: int) -> int:
    """Require an integer rank 1 <= k <= len(nums); duplicates count."""
    heap: list[int] = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]                              # k-th largest = smallest in the heap of top K
 
 
# ------------------------------------------------------------------
# 3) Streaming median — two heaps trick
# ------------------------------------------------------------------
class MedianFinder:
    """Add numbers one at a time, get median in O(1), insert in O(log n).
 
    Trick: two heaps.
      - lower: max-heap of the smaller half (stored as negated values in Python's min-heap)
      - upper: min-heap of the larger half
    Invariants: every lower value <= every upper value;
    len(lower) == len(upper) or len(lower) == len(upper) + 1.
    median() requires at least one added integer and returns a float.
    """
    def __init__(self) -> None:
        self.lower: list[int] = []              # max-heap (negated)
        self.upper: list[int] = []              # min-heap
 
    def add(self, num: int) -> None:
        # Push into the correct half
        if not self.lower or num <= -self.lower[0]:
            heapq.heappush(self.lower, -num)
        else:
            heapq.heappush(self.upper, num)
        # Rebalance so sizes differ by at most 1, and lower may be exactly one larger
        if len(self.lower) > len(self.upper) + 1:
            heapq.heappush(self.upper, -heapq.heappop(self.lower))
        elif len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))
 
    def median(self) -> float:
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])
        return (-self.lower[0] + self.upper[0]) / 2
 
 
# ------------------------------------------------------------------
# 4) Merge K sorted lists — heap of head pointers
# ------------------------------------------------------------------
def merge_k_sorted(lists: list[list[int]]) -> list[int]:
    """Sorted inputs; O(k + n*log(k+1)) time, O(k) heap + O(n) output."""
    heap: list[tuple[int, int, int]] = []       # (value, list_idx, item_idx)
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
 
    out: list[int] = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out
 
 
# ------------------------------------------------------------------
# 5) Dijkstra's shortest path — heap of (dist, node) with lazy deletion
# ------------------------------------------------------------------
def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, float]:
    """Finite graph, integer node labels, nonnegative integer weights.
 
    Returns distances for reachable nodes only; no input validation.
    Integer accumulation is exact; lazy heap entries can use O(E) space.
    """
    dist: dict[int, float] = {start: 0}
    heap: list[tuple[float, int]] = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                            # stale entry — skip
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist
 
 
# ------------------------------------------------------------------
# 6) Event scheduler — priority queue by run-at timestamp
# ------------------------------------------------------------------
class Scheduler:
    """Minimal cron-like scheduler. Heap of (run_at, id, callback)."""
    def __init__(self) -> None:
        self._heap: list[tuple[float, int, Any]] = []
        self._next_id = 0
 
    def schedule(self, run_at: float, callback) -> None:
        heapq.heappush(self._heap, (run_at, self._next_id, callback))
        self._next_id += 1                      # tie-breaker to keep tuples comparable
 
    def next_due(self, now: float):
        """Return the next callback due by ‘now’, else None."""
        if self._heap and self._heap[0][0] <= now:
            return heapq.heappop(self._heap)[2]
        return None
 
 
if __name__ == "__main__":
    print("top_k_frequent [1,1,1,2,2,3] k=2 :", top_k_frequent([1, 1, 1, 2, 2, 3], 2))
    print("kth_largest [3,2,1,5,6,4] k=2 :", kth_largest([3, 2, 1, 5, 6, 4], 2))
 
    mf = MedianFinder()
    for x in [1, 5, 2, 10, 7]:
        mf.add(x)
    print("median after [1,5,2,10,7]:", mf.median())     # 5
 
    lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
    print("merge_k_sorted :", merge_k_sorted(lists))
 
    graph = {
        1: [(2, 7), (3, 9), (6, 14)],
        2: [(3, 10), (4, 15)],
        3: [(4, 11), (6, 2)],
        4: [(5, 6)],
        5: [],
        6: [(5, 9)],
    }
    print("dijkstra from 1 :", dijkstra(graph, 1))       # {1:0, 2:7, 3:9, 4:20, 6:11, 5:20}
 
    sched = Scheduler()
    sched.schedule(100, lambda: "task A")
    sched.schedule(50, lambda: "task B")
    print("next_due at t=60 :", sched.next_due(60)())     # task B (earlier)

Anatomy of the script

What each function teaches

Name: top_k_frequent

Desc: Count n occurrences into u values, then retain min(K,u) frequency/value pairs. Expected O(n + u log(min(K,u)+2)) time and O(u) total state; tied counts prefer larger values in this code.

Name: kth_largest

Desc: Same shape as top-K but return just the smallest in the surviving heap.

Name: MedianFinder

Desc: The two-heap trick: max-heap of the lower half + min-heap of the upper half. Median = top of one (odd count) or average of both tops (even count). Insertion O(log n), median query O(1), total state O(n).

Name: merge_k_sorted

Desc: Keep one head per nonempty sorted list. Scanning k inputs plus n outputs costs O(k + n log(k+1)); heap space O(k), returned output O(n). This is the merge mechanism, not an external file-I/O implementation.

Name: dijkstra

Desc: Priority-queue Dijkstra with lazy deletion (‘if d > dist[u], skip’). Cleaner than the classic decrease-key version and equally correct.

Name: Scheduler

Desc: Heap keyed by (run_at, tiebreaker, callback). The tiebreaker matters — without it, Python tries to compare callbacks for ties and TypeErrors.

What to observe when you run it

top_k_frequent returns [2, 1] (values with counts 2 and 3 — the two most frequent). kth_largest of [3,2,1,5,6,4] with k=2 = 5. MedianFinder tracks the running median correctly through non-sorted inputs. merge_k_sorted returns [1,2,3,4,5,6,7,8,9] from three interleaved lists. dijkstra from node 1 produces distances to all reachable nodes. Scheduler pops the earlier task even though task A was scheduled first.

Goal: Implement ‘K-closest points to origin’ using a max-heap of size K

Hint: Use squared distance (avoid sqrt). Push (-dist, point) so the FARTHEST is at the top; when the heap exceeds K, pop it. What remains = K closest. O(n log(K+2)) worst-case selection work, potentially preferable to full sorting when K is small.

def k_closest(points: list[tuple[int, int]], k: int) -> list[tuple[int, int]]:
    import heapq
    heap: list[tuple[int, tuple[int, int]]] = []
    for x, y in points:
        d = x*x + y*y                                    # squared distance — no sqrt
        heapq.heappush(heap, (-d, (x, y)))              # negate so max is at top
        if len(heap) > k:
            heapq.heappop(heap)
    return [p for _, p in heap]
 
print(k_closest([(1, 3), (-2, 2), (5, 8), (0, 1)], 2))   # e.g. [(-2, 2), (0, 1)]

Exercise answer: squared distances for (1,3), (-2,2), (5,8), (0,1) are 10, 8, 89, 1; retain the last and (-2,2). The output is heap order, not increasing distance. K is a nonnegative integer; K=0 returns [], K beyond input length retains all, and repeated points remain repeated. With equal distances this tuple ordering retains lexicographically larger points, not arrival-order ties. Cost is O(n log(min(K,n)+2)) time and O(min(K,n)+1) heap state under unit-cost integer arithmetic.

Contracts, stability and empty inputs

top_k_frequent requires nonnegative integer K, retains min(K,u) distinct values and does not sort its result. kth_largest requires 1 ≤ K ≤ len(nums): duplicates occupy separate ranks; other ranks are outside its contract, not implicitly validated. MedianFinder.median() on empty state raises IndexError; its float return can round very large integers or overflow converting an enormous integer, although partition comparisons remain exact. merge_k_sorted requires each input sorted in nondecreasing order, retains duplicates and does not mutate inputs; equal heads are ordered by list index and then position.

The scheduler returns the original callback object without calling it; callbacks should be callable and run_at/now must be finite comparable timestamps in one clock domain. It is a synchronous due-queue model: no sleep loop, cancellation, durability, concurrency or delivery guarantee. Its unique counter makes equal timestamps FIFO and keeps callback objects out of comparison. Empty/no-due returns None. A heappush that raises while comparing a bad payload may already have appended it: do not continue using a heap after catching TypeError without repairing the state.

Dijkstra here uses integer node labels to make equal-distance heap tuples comparable, nonnegative integer weights and exact integer accumulation (rather than starting with 0.0 and rounding weights above 2**53). The graph is read-only; missing adjacency means no outgoing edges. Negative weights and negative cycles are not validated: this re-relaxing variant may happen to recover some negative-edge answers but loses Dijkstra's settled-distance proof and complexity guarantee, and can loop on a reachable negative cycle.

(d) Production reality · 15 min

A scheduler is more than its heap

Python's sched implementation stores (time, priority, sequence, action, argument, kwargs) events in a heap. A next-due check avoids repeatedly scanning every pending job, but running callbacks, clock selection and overload policy remain separate concerns. Our Scheduler intentionally demonstrates only stable ordering and the due boundary; it is not evidence that Airflow, cron and every distributed job runner share its implementation or throughput.

Routing: weights first, acceleration second

For A→C with cost 10 versus A→B→C with cost 2, fewest hops is not cheapest travel. A nonnegative weighted model permits Dijkstra. A* additionally needs a suitable heuristic and correct reopening policy; preprocessing such as contraction hierarchies is a further engineering choice, not something this lab implements or an assertion about a proprietary route service. More efficient frontier selection does not repair an incorrect cost model.

Equal priorities: a reproducible failure and repair

heapq.heappush(h, (1, object())) twice can raise TypeError because equal first fields force comparison of opaque second fields. (1, sequence, payload) prevents that comparison when sequence is unique. Stability is a specified policy, not a property of heapify itself; payloads can safely be the same object more than once. The CPU tests exercise equal-time callbacks by identity and exact return order.

Where this shows up in the rest of the plan

Root: Heaps power ‘the next best thing’ everywhere

Label: S030 · Graphs (Dijkstra, A*)

Desc: Nonnegative weighted Dijkstra can use a heap; unweighted BFS instead uses a FIFO queue.

Label: S031 · Sorting (heapsort)

Desc: O(n log n) sort by heapifying + n pops.

Label: S033 · DP (top-K DP states)

Desc: Beam search retains only K partial candidates and is heuristic pruning, not generally exact dynamic programming. A heap is one possible selection implementation.

Label: Further connection · Event-time stream processing

Desc: Event-time buffers can use priority queues, but a watermark/late-data policy is separate; Kafka partition ordering is not a global heap-order guarantee.

Label: Further connection · Beam search in sequence models

Desc: Decoders select K candidate sequences using heaps, sorting or tensor top-k operations; no unique implementation follows from the algorithm name.

Label: Further connection · Rate limiting and expiry

Desc: Expiry scheduling may use a heap; token buckets can instead use a token count and elapsed-time arithmetic, and ordered sliding windows may use a deque.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — questions and worked answers

Q: State the min-heap invariant in one sentence.

A: Every parent's value is less than or equal to both of its children's values. The root is therefore the minimum.

Q: Why is a binary heap stored in an ARRAY, not a tree of nodes?

A: Its complete shape can be encoded without child pointers: children 2i+1 and 2i+2 if in bounds, parent (i−1)//2 for i>0. Python lists hold contiguous references to separately allocated objects, so this is not a claim that payloads are inline or that allocations disappear.

Q: What are the time complexities of insert, peek-min, and pop-min?

A: Insert: O(log n) — sift-up. Peek-min: O(1) — just look at index 0. Pop-min: O(log n) — replace root with last, sift-down.

Q: How do you simulate a max-heap using Python's heapq?

A: Push -x instead of x; negate on pop. For tuples, use (-key, value) only if tied values are comparable; otherwise (-key, counter, payload). Python 3.14 adds max-heap APIs; negation works on earlier versions too.

Q: For top-K frequent values, how do n input occurrences, u distinct values and K affect heap versus sort costs?

A: Counting costs expected O(n) time and O(u) storage. Heap selection adds O(u log(min(K,u)+2)) time and O(min(K,u)) heap state, versus O(u log u) sorting. The O(u) counts remain either way; a speedup must be measured, and output sorting is additional work.

Q: Explain the two-heap trick for streaming median.

A: Max-heap for the lower half, min-heap for the upper half. Keep sizes balanced (differ by at most 1). Median = top of the larger heap (odd count) or average of both tops (even count). Insertion O(log n), median query O(1); every lower value must also be ≤ every upper value. All n stream values are retained.

Q: Why do heap-based algorithms (Dijkstra, A*) use ‘lazy deletion’?

A: heapq has no position-indexed decrease-key. Lazy replacement pushes a better entry and later skips stale ones. An indexed heap can update in O(log V) while retaining O(V) entries; this lazy implementation can hold O(E), with a log(E+2) factor. Similar simple-graph time shorthand does not imply equal storage.

Q: Give the outline of Dijkstra's algorithm using a min-heap.

A: Initialise dist[start] = 0, heap = [(0, start)]. Loop: pop (d, u); if d > dist[u], skip. Else for each neighbor v with edge weight w, if d + w < dist[v], update and push (new_dist, v). Repeat until heap empty.

Q: What's the common Python heap gotcha with tuple comparison?

A: If two tuples have the same first element, heapq compares the SECOND element. If that's a non-comparable object, TypeError. Fix: always include a monotonically-increasing tiebreaker (like next(itertools.count())) in the middle.

Q: Stretch — heapify a random array in O(n), not O(n log n). Explain how.

Stretch: true

A: Bottom-up: for each non-leaf node from index n//2 − 1 down to 0, call sift-down. The total cost sums to O(n), not O(n log n), because most nodes are near the bottom (short sift-down paths). Python's heapq.heapify(list) does exactly this in-place.

Explain-out-loud test

Teach these three in one minute each, no notes:

1. What's a heap, and what one thing does it do well?
2. Why is a heap stored in an array instead of a tree with pointers?
3. Give a real production system that uses a heap — and why.

Grind this pattern in the LeetCode track

This session builds the mental model for heaps & top-k. The full pattern treatment — templates, five graded problems each, and the design review follow-ups — lives in the dedicated LeetCode series:

L26 · Heaps & Top-K

Do the concept here, then go there to build the reflex.

Explain-out-loud answer guide

1. A binary heap enforces parent ≤ child and completeness, giving O(1) minimum peek, O(log n) worst-case sift work, and O(n) bottom-up construction. It is not globally sorted or stable by itself.
2. Complete shape makes child/parent positions calculable; Python uses an array of references rather than child-linked node objects. The comparison contract still matters.
3. Python sched is a concrete priority-queue application: earliest event, then priority, then sequence. Our due-queue model tests that ordering but does not reproduce a production scheduler.

What comes next

Next: S030 · Graphs — Representation, BFS, DFS, Shortest Path

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

Primary passages checked 2026-10-10; saved raw/canonical evidence and bounded exact-program tests support the named contracts, not production benchmarks or whole-site approval.

• Python 3.14 heapq: invariants, max-heaps and priority queue notes
• Python 2.3: new heapq module
• CPython 3.14 sched implementation