Front Or Back

A robot drives on a grid. Continuing straight costs 0, turning 90 degrees costs 1. Your state is (cell, heading), so every edge weighs 0 or 1. You solve it with a binary heap in $O(E \log V)$ .

A teammate swaps the heap for a deque: on a 0-weight edge they push_front, on a 1-weight edge they push_back, and they pop from the front. Same answers, and measurably faster on the same input.

What makes the deque version correct?

The state graph is planar and distances are bounded by rows plus columns, so a counting sort on distance replaces the heap.

At every moment the deque holds at most two distinct distance values, $d$ and $d+1$ , with all the $d$ entries ahead of all the $d+1$ entries. A 0-edge out of the front vertex produces distance $d$ , which belongs at the front; a 1-edge produces $d+1$ , which belongs at the back. The deque stays sorted, which is the only service the heap was providing.

Each vertex enters the deque exactly once, as in ordinary BFS, so no stale entry can ever be popped and no distance check is needed on pop.

All the weights are non-negative, which is the same condition Dijkstra's greedy argument needs, so any FIFO structure works.