Unit 2.6 · about 4 h
101 / 324Heaps and priority queues
Heaps buy priority operations in logarithmic time with plain array storage. The linear build and the two-heap median are the two derivations that recur everywhere else.
- derive
- implement
You can now
- Derive why bottom-up heap construction is linear while repeated insertion is \(\Theta(n \log n)\).
- Implement sift-up, sift-down, Floyd build,
push,popandreplacewith invariant tests, usingheapqonly as an oracle. - Implement the two-heap streaming median and defend its size and ordering invariants.
Covers
- Heap order, bottom-up construction and mutable priorities
Study, in this order
2 steps
- Heaps and priority queuesDSA Handbook - search, trees and heaps
What a heap actually is; The two primitives; The full operation table; Building a heap in linear time; Worked example: LC 295; Where readers go wrong
Depth · Skim the LC 215 and LC 23 worked examples; kth-largest belongs to the quickselect unit and k-way merge is not assigned.
- Two-heap median archetypes: when one heap is not enoughDSA Handbook Patterns - two-heap median archetypes
Streaming median (two-heap balance invariant); Variants side-by-side
Depth · Skip sliding-window median and the sketch survey; only the append-only variant is implemented here.
Focus on
- Most nodes are leaves with short subtrees: level \(h\) holds about \(n/2^{h+1}\) nodes at \(O(h)\) sift cost each, and the series \((n/2)\) times sum \(h/2^h\) converges to \(O(n)\). Repeated insertion instead pays \(\log 1 + \ldots + \log n = \log(n!))\), which is \(\Theta(n \log n)\).
- Floyd starts at
n//2 - 1, the last internal node, and moves right to left so every sift-down sees valid child heaps. That order is theMAX-HEAPIFYprecondition; building by sift-up throws the linear bound away. - Two-heap invariants:
0 <= len(lower) - len(upper) <= 1with the extra element in lower, andmax(lower) <= min(upper). Push-then-rotate maintains both with \(O(\log n)\) per insert and \(O(1)\) per query. heapqis min-heap only andheapifyruns in documented \(O(\operatorname{len}(\text{heap}))\) time. Max-heap idioms negate keys, and payloads need a tiebreak slot (the LC 23 tuple trick) so equal priorities never compare task objects.
Reproduce closed-book
push and pop. With random.seed(0) and random.sample(range(10**6), 2000), assert the result is a valid max-heap holding the same multiset, and count comparisons (at most \(2n = 4000\)). Implement MedianFinder with the push-then-rotate rule: after add(1) and add(2) the median is 1.5; after add(3) it is 2.0. Differential-test both against heapq and brute-force medians on random streams.Traps
- Calling sift-down on a node whose children are not heaps yet. The child-heaps precondition is load-bearing; Floyd's right-to-left order is what establishes it.
- Rebalancing the two heaps in the wrong order. Push to lower, move its top to upper, then rotate back only if upper outgrew lower; skipping the last step breaks the size invariant on even totals.
- Averaging the two middle values with
//instead of/. Floor division truncates the even-case median (1.5 becomes 1).
Practice
LeetCode 703: Kth Largest Element in a Stream
Size-k min-heap with heapreplace; include k=1 and duplicate-heavy streams
After submitting, read the AlgoMaster write-up for Kth Largest Element in a Stream (https://algomaster.io/learn/dsa/kth-largest-element-in-a-stream).
LeetCode 295: Find Median from Data Stream
Two-heap MedianFinder; example sequence add(1), add(2), findMedian expects 1.5, then add(3), findMedian expects 2.0
Attempt cold. After submitting, read the AlgoMaster write-up for Find Median from Data Stream (https://algomaster.io/learn/dsa/find-median-from-data-stream).
Self-test
-
Prove Floyd's build is \(O(n)\).
Nodes at height \(h\) number about \(n/2^{h+1}\) and each costs at most \(h\) sift steps. The total is at most \((n/2)\) times the sum of \(h/2^h\) over all \(h\), and that series converges to 2, giving at most about \(n\) sift steps and \(2n\) comparisons. Naive repeated insertion instead pays \(\log 1 + \ldots + \log n = \log(n!)\), which is \(\Theta(n \log n)\) by Stirling. -
Why must the build loop start at
n//2 - 1and go down?Indices[n//2, n)are leaves, which are trivially valid single-element heaps, son//2 - 1is the last internal node. Descending guarantees both children are already valid heaps when a node is sifted, which is the sift-down precondition. -
State both two-heap invariants and compute the median for odd and even totals.
Size: lower holds at most one element more than upper, never fewer. Ordering: every lower key is at most every upper key. Odd total: the median is lower's root. Even total: the average of the two roots. -
heapqhas no max-heap. How do you store(priority, task)pairs, and what breaks on ties?Push(-priority, index, task)with a tiebreak counter: negation flips the order and the counter keeps task objects uncompared. Without it, equal priorities fall through to comparing tasks, which raisesTypeErrorfor unordered types.
Completion criterion
Stop when
Floyd build holds heap order with at most 2n comparisons on the 2000-element seed-0 input, the median matches brute force on random streams, and you can state both invariants plus the linear-build series without notes.
Mark passed, then open 2.7 Only mark this when you can do it without notes.Leads to
- 2.2 Partitioning, quicksort, quickselect and top-k Return there for the top-k routing decision between heaps and quickselect.
- 3.6 Dijkstra, Bellman-Ford and negative cycles Dijkstra consumes a priority queue with stale entries.
Comes after
- 1.6 Stacks, queues, deques and monotone structuresHeaps are the \(O(n \log n)\) lazy-deletion alternative the deque beats on windows.
- 2.1 Sorting contracts, lower bounds and merge sortHeap sort reuses the heap built there.
- 2.2 Partitioning, quicksort, quickselect and top-kThe heap side of the top-k trade-off.
- 2.5 Binary search trees, balance and augmented treesHeaps serve priority workloads where ordering is partial, not total.
- 2.8 Interval ordering, merging and sweep linesConcurrency counting reuses the heap as its active set.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.