A heap exists for one question: which unvisited node is nearest?

Dijkstra's algorithm asks it at every step. transit — the Vilnius public transport journey planner — runs Dijkstra for every query, so for it the question is not academic.

In lessons 14 and 15 you will write that algorithm. This step shows what the queue you put it on costs.

Is a heap needed at all

The simplest way to find the nearest is to look at all of them and take the smallest. O(n) instead of O(log n), but with no structure at all.

Our capture (docs/reference/transit-benchmarks.md, the same query):

Dijkstra's queue	our time	against the hand-written heap
linear minimum scan	876.6 ms	16.4× slower
hand-written binary heap	53.4 ms	1.0 (baseline)
container/heap	73.1 ms	1.37× slower

The first row is the answer to why this lesson exists. Nearly a second against fifty milliseconds — to a user that is the difference between "it works" and "it froze".

And the second row is what you just measured

container/heap loses there too. Four independent measurements:

source	ratio
transit's README	1.7×
our transit capture, CLI	1.37×
our transit capture, BenchmarkRouter	1.67×
your algo pq, step 6	1.66×

A different program, different data, a different element type — and the same answer. Step 6 showed why, and that is exactly why it repeats: boxing and table dispatch do not depend on the task or on the machine.

Compare with lesson 6's trie argument, which inverted between machines. There the difference was a tenth of a millisecond and a change of processor carried it away. Here the cause is 20,000 allocations, and those do not go anywhere.

Measure when you do not know the cause of a difference. Once you know it, reproducibility becomes predictable.

And one row this lesson will not explain

The same table has a fourth option:

| Connection Scan | 0.70 ms | 76× faster than the best Dijkstra |

With no queue. No heap.

How can a well-implemented Dijkstra be beaten 76× by giving up the structure you have just built? The answer is lesson 15, and it is not "the heap was bad". For now, only this: the fastest way to answer a question is sometimes to ask a different one.