Heaps

Python · Unit 24: Data structures

Sometimes what matters isn't who arrived first, but what is most urgent. That's what a heap is for: a list that always hands back the smallest.

The heapq module handles it: heappush puts a value in and heappop takes the smallest out, no matter when it went in.

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
print(heapq.heappop(h))

Prints

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
What does this code print?
2. Complete the code
Take out the most urgent one. It should print: 1
3. Predict the output
heapify turns a list you already have into a heap. What does it print?
4. Multiple choice
You push 5, 1 and 3 into a heap with heappush. What can you be sure of about the list?
5. Find the bug
It should print the smallest number in the heap. Which line has the error?
6. Predict the output
The 1 is the most urgent. What does it print?
7. Put the lines in order
Put urgent(tasks) together; it takes [priority, task] pairs and returns the name of the most urgent one.
8. Find the case that fails
most_urgent(nums) should return the smallest number in the list, or 0 if the list is empty. Which call breaks it?
9. Predict the output
Tasks go in and out mixed together. What does it print?

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.