deque and heapq
In short: collections.deque is a list built for pushing and popping either
end in constant time — list.pop(0) shifts every remaining item and gets slow on
a long list, deque.popleft() never does. heapq turns a plain list into a
min-heap: heappush/heappop keep the smallest item always reachable in
O(log n), which is how you build a priority queue without sorting after every
change. A deque(maxlen=n) silently drops from the far end once it's full — useful
for a bounded history, dangerous if you expected an error instead. Reach for a deque
when you add/remove from both ends; reach for a heap when you always need "the
smallest (or largest) next," not the whole thing sorted.
Undo history for a text editor
An editor keeps the last few actions so Ctrl+Z has something to undo. A plain list
works, but popping the oldest action off the front is slow once the list is long
— every remaining item has to shift over one slot. deque avoids the shift:
A bounded history is even more useful — keep only the last 3 actions, automatically:
from collections import deque
history = deque(maxlen=3)
for action in ["type a", "type b", "type c", "type d"]:
history.append(action)
print(list(history))A hospital triage queue
Patients don't arrive in the order they should be seen — a 1 (most urgent) should
jump ahead of a 2 that arrived first. heapq keeps the smallest priority number
on top no matter what order things were pushed in:
heapq compares the whole tuple, so on a tied priority it looks at the next
element to break the tie. That's fine for two numbers — it breaks the moment the
second element isn't comparable, like two dicts:
import heapq
heap = []
heapq.heappush(heap, (2, {"name": "Asha"}))
heapq.heappush(heap, (2, {"name": "Bea"}))
heapq.heappop(heap)A running counter fixes it — ties now break by arrival order, and the payload can be anything:
Merge two sorted leaderboards
Two already-sorted lists need to become one sorted list — say, scores from two game
servers. Sorting the combined list again throws away work you already paid for;
heapq.merge combines sorted inputs in one pass without re-sorting:
heapq also has two shortcuts for "give me the extremes without sorting the whole
list": nlargest(n, items) and nsmallest(n, items).
Quick practice
from collections import deque
dq = deque([2, 3, 4])
dq.appendleft(1)
dq.append(5)
print(dq.popleft(), dq.pop())This prints 5, not the smallest value in the list. Heapify it first.
🎯 Your turn
Write triage_order(patients). Each patient is [priority, name] — a lower
number is more urgent. Return the names in the order they should be seen: by
priority first, and by arrival order (their position in the list) for a tie.
triage_order([[2, "Asha"], [1, "Bea"], [2, "Cy"]])→["Bea", "Asha", "Cy"]triage_order([])→[]
Hint: push (priority, index, name) onto a heap as you loop with enumerate,
then heapq.heappop() everything off in order and collect the names.
Press ▶ Run and hit ✓ Check. ✅