Heaps + Priority Queues — the O(log n) sorted-ish structure
Heaps + Priority Queues
A heap is a binary tree flattened into an array where every parent is smaller than its children (min-heap). You lose full ordering but gain two cheap ops: peek min in O(1), push/pop in O(log n). That trade shows up in Dijkstra, A*, event simulators, top-K, streaming medians.
Python ships one: heapq. No Heap class — functions operate on a regular list you promise to only mutate through them.
How it works
The array h represents a tree where children of index i sit at 2*i+1 and 2*i+2. Push appends and bubbles up. Pop returns h[0], moves last to front, sifts down.
heapify is O(n), not O(n log n) — bottom-up bubble. Always heapify existing data; don't push in a loop.
Max-heap: negate keys. Priority queue: push tuples (priority, task). Add a sequence counter as second field so ties never fall through to comparing payload.
Common bugs
- Sorting a heap. Only
nums[0]is guaranteed smallest. - Mutating the list directly.
h.append(x)breaks invariant. - Uncomparable payloads.
(prio, dict)blows up on a priority tie. Insert a sequence number. - Rebuilding every insert. Push/pop, don't heapify in a loop.
Try it
- Change starter to keep a running top-3 as numbers stream in. Hint: push, then heappop when heap exceeds size 3.
- Build a task scheduler using
(run_at, seq, name). Confirm same-timestamp tasks come out in insertion order.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Use the
heapqmodule to writek_smallest(nums, k)that returns theksmallest numbers fromnumsin ascending order. - Exercise 2
Write
merge_sorted(lists)that takes a list of already-sorted lists and returns a single sorted list containing all their elements. Useheapq.mergeor a min-heap. - Exercise 3
Write
running_medians(stream)that returns a list where elementiis the median ofstream[:i+1]. Use two heaps (max-heap for lower half, min-heap for upper half) so each step is O(log n).