What is heapq?

Keys: ← → step, space play (for the part you clicked last).

1. The idea in 10 seconds

A normal queue (list.pop(0)) is a line at the bakery: whoever came first goes first.

heapq is the emergency room: whoever is most urgent goes first, no matter when they arrived. "Most urgent" means smallest. For a tuple, Python compares the first value first, so (1, 's') < (2, 'a') < (2, 'r').

For us, smallest = earliest turn. That's why the queue stores (turn, zone) with the turn in front.

2. Same pushes, different pops

Both boxes get the same 5 items in the same order. Then 3 pops. Watch which item comes out.

3. Why it matters: your _search on a tiny map

Two ways to the goal: s → r → g, where r is restricted (2 turns), arriving at turn 3; or s → a → g, arriving at turn 2. The fast way is the one through a.

Your search stops at the first goal it pops. So the question is just: which goal state gets popped first?

4. On the real maps (all 5–25 drones)

Same search code, only the queue type changed. Measured with the prototype:

Without restricted zones every move costs 1, so the bakery line is already in turn order. That's why FIFO was fine until now.