Python for Interviews

heapq & bisect

Priority queues with heapq and binary search on sorted lists with bisect.

Medium, about 45 minutes to practise.

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

start

Heap is empty.

Empty heap. We will push 3, 1, 4 with heappush.

h = []

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.

  1. Push each onto a min-heap; after all three, heap[0] is 1. For a max-heap of scores, push -score and negate on pop.
  2. Keep sorted_scores = [1, 3, 4]. bisect_left(sorted_scores, 3) returns 1, one score is strictly smaller.
  3. bisect_right(sorted_scores, 3) returns 2, use it when ties should sit after equal values.

In code:

  • import heapq, bisect
  • h = []
  • 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.

All lessons