Heaps with heapq

A heap is a tree-based structure that always keeps the smallest element ready at the front, and Python's heapq module turns an ordinary list into a binary min-heap so you can push and pop the minimum in fast O(log n) time.

Learn Heaps with heapq in our free Python course — an interactive lesson with runnable examples, a practice exercise and a quick reference.

Part of the free Python course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Heaps power priority queues, scheduling, and "top-k" queries. Once you see how heapq works, a whole class of problems becomes easy.

A heap lives in a plain list. heappush adds an item keeping the heap valid, heappop always removes the smallest, and heapify rearranges an existing list into a heap in place:

Need just the biggest or smallest few from a large collection? heapq.nlargest(k, data) and nsmallest(k, data) do it in O(n log k) — faster than a full sort when k is small. Both accept a key function just like sorted() :

For a million records where you only need the top 10, nlargest(10, data) keeps a heap of just 10 items as it scans once — far cheaper than sorting all million.

Push (priority, item) tuples and the heap orders by priority automatically, because Python compares tuples left to right. Add a tie-breaking counter so the heap never compares the items themselves:

Replace each ___ so the code pushes tasks by priority and pops the most urgent first.

❌ Tuples whose items can't be compared on a tie

heapq even has merge() , which lazily merges already-sorted inputs into one sorted stream — exactly how external merge sort works on huge files.

Lesson complete — priority queues hold no fear!

You can push and pop the minimum with heappush / heappop , build a heap with heapify , grab the top-k with nlargest / nsmallest , build priority queues from tuples, and flip to a max-heap with the negation trick.

🚀 Up next: Binary Search with bisect — find and insert into sorted data in O(log n).

Practice quiz

Is Python's heapq a min-heap or a max-heap?

  • A max-heap — the largest pops first
  • Neither; it is a balanced tree
  • A min-heap — the smallest pops first
  • It depends on insertion order

Answer: A min-heap — the smallest pops first. heapq is always a min-heap: the smallest value sits at index 0 and pops out first.

After heappush'ing 5, 1, 8, 3 onto an empty heap, what is heap[0]?

  • 1
  • 5
  • 8
  • 3

Answer: 1. The smallest pushed value, 1, is always kept at index 0 of the heap.

What does heapq.heappop(heap) return?

  • The largest element
  • The last element pushed
  • A random element
  • The smallest element

Answer: The smallest element. heappop removes and returns the smallest element each time, in O(log n).

What does heapq.nlargest(3, [88, 42, 71, 99, 63, 55, 100, 30]) return?

nlargest returns the top k values in descending order: 100, 99, 88.

What does heapq.nsmallest(3, [88, 42, 71, 99, 63, 55, 100, 30]) return?

nsmallest returns the bottom k values in ascending order: 30, 42, 55.

What does heapify do to a list?

  • Fully sorts it in place
  • Returns a new sorted list
  • Rearranges it into a valid heap in place in O(n)
  • Removes duplicates

Answer: Rearranges it into a valid heap in place in O(n). heapify reorders the list in place into a heap in O(n); only the smallest is guaranteed at index 0.

Is a heap list (after heapify) guaranteed to be fully sorted?

  • Yes, always
  • No, only the smallest is guaranteed at index 0
  • Yes, in descending order
  • Only if all values are unique

Answer: No, only the smallest is guaranteed at index 0. A heap only guarantees the smallest at index 0; to get sorted output, heappop repeatedly.

How do you make a max-heap behavior with heapq?

  • Use heapq.maxheap()
  • Sort the list first
  • Use heappop twice
  • Push the negated values and negate again when popping

Answer: Push the negated values and negate again when popping. There is no built-in max-heap; push -x and negate on the way out, or use nlargest.

When building a priority queue, why add a tie-breaking counter to (priority, item) tuples?

  • To make popping faster
  • So the heap never has to compare the items themselves when priorities tie
  • To sort the items alphabetically
  • To save memory

Answer: So the heap never has to compare the items themselves when priorities tie. A unique counter breaks ties so Python never compares the items, which could raise a TypeError.

When is nlargest(k, data) preferable to fully sorting the data?

  • When you need every element ordered
  • When the data is already sorted
  • When you only need the top few from a large collection (O(n log k))
  • When k equals the length of the data

Answer: When you only need the top few from a large collection (O(n log k)). nlargest keeps a heap of size k and runs in O(n log k), cheaper than a full O(n log n) sort when k is small.