1Understand
The idea
heapq is Python's binary heap. The smallest item is always at index 0, and every heappush / heappop restores that property in O(log n). heapify turns an existing list into a heap in O(n), which is cheaper than pushing items one by one.
It is a min-heap only. There is no max-heap type: push −x (or a tuple whose first field is negated) and negate again when you pop. For ties, store (priority, tie_breaker, payload) so comparisons never try to order incomparable objects.
bisect answers "where does this value belong in a sorted list?" in O(log n). That is how you count how many elements are smaller than x, or find the insertion point, without scanning. Remember: the search is O(log n), but inserting into a Python list at that index is still O(n).
Intuition
heapq is a binary min-heap living in a plain list: index 0 is always the smallest. heappush and heappop are O(log n). There is no max-heap; push negated numbers (or tuples with a negated first field) when you need largest-first.
bisect_left / bisect_right binary-search a sorted list for the insertion point in O(log n). That answers "how many are < x" or "where would x go" without a linear scan.
The heap list is not fully sorted, only the heap property holds, so never binary-search a heap as if it were sorted.
What you will be able to do
- Push and pop with heapq (min-heap)
- Simulate a max-heap by negating
- Find insertion points with bisect_left/right
2See it
Walkthrough
Min-heap push and peek
Push 3, then 1, then 4. Index 0 is always the smallest.
1 / 5
Heap is empty.
Empty heap. We will push 3, 1, 4 with heappush.
Heap push/pop are O(log n); heapify is O(n). bisect_* is O(log n) but requires a sorted array, inserting into a sorted list is O(n). For streaming top-k, a bounded heap of size k is O(n log k).
Read the walkthrough as text
Running smallest and insertion rank. Scores arrive as 3, 1, 4.
- Push each onto a min-heap; after all three,
heap[0]is1. For a max-heap of scores, push-scoreand negate on pop. - Keep
sorted_scores = [1, 3, 4].bisect_left(sorted_scores, 3)returns1, one score is strictly smaller. bisect_right(sorted_scores, 3)returns2, use it when ties should sit after equal values.
In code:
import heapq, bisecth = []for x in [3, 1, 4]:heapq.heappush(h, x)
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
heappush / heappop
Example. Process tasks in ascending priority order.
How. heap = []; heappush(heap, x); x = heappop(heap) always returns the smallest item.
heapify and nlargest
Example. K largest elements without full sort.
How. heapify in O(n); heapq.nlargest(k, a) beats sorting the whole array when k is small.
Max-heap by negation
Example. Always pick the largest remaining value.
How. Store -x on push; pop returns -heappop(heap) so the underlying structure stays a min-heap.
Tuples as heap items
Example. Tie-break equal priorities by insertion order or secondary key.
How. heappush(heap, (priority, tie_key, payload)), Python compares tuples lexicographically.
bisect_left vs bisect_right
Example. Where to insert x to keep a sorted list, or count equal values.
How. bisect_left is before equals; bisect_right is after; bisect_right - bisect_left counts x.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Expecting heapq to be a max-heap
Why it happens. “Pop the biggest” sounds like a max-heap, but heapq is documented as min-first.
How it fails. heappush(h, 5); heappush(h, 1); heappop(h) returns 1 when you wanted 5 first.
Fix. Negate on insert and negate again on pop, or use nlargest/nsmallest when you only need a few extremes.
Treating the heap list as sorted
Why it happens. After many pushes, the heap list looks sorted enough to binary search.
How it fails. bisect(heap, x) while the array is only heap-ordered, wrong position and broken heap invariant.
Fix. heappop until empty for sorted order, or maintain a separate sorted structure for search.
Using bisect_left where bisect_right is needed
Why it happens. bisect_left and bisect_right only differ in edge cases, so either feels fine.
How it fails. Inserting duplicate 5 with bisect_right when you need stable “before existing equals” puts after all 5s.
Fix. New value before existing equals → bisect_left; after → bisect_right; count equals with right, left.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.