This lesson answers a question lesson 3 asked and lesson 6 refused to answer.

In lesson 3 you built your own doubly linked list and compared it with container/list:

                             walk/shift pointer writes
slice (shift)                        44              0
Playlist (ours)                      50              4
container/list                       50       (hidden)

A tie. To within one hop.

In lesson 6 you compared your binary search with sort.Search:

                        comparisons        ns/op
hand-rolled LowerBound            7           18
sort.Search                       7           15

The standard library won. And that lesson closed like this:

Does that mean the standard library is always at least as good? It sounds reasonable. But in lesson 13 you will build a heap by hand and compare it with container/heap — and the answer will be the opposite, clearly and measurably.

This is that lesson.

Guess before you read on

You will build a binary heap — the prerequisite lessons 14 and 15 need — and compare it with container/heap. Same algorithm, same comparison count.

By what factor will the times differ, and in which direction?

Write it down. Step 6 measures it, and step 7 shows why three answers can differ and all three be right.

And why a heap at all

Not for the standard-library argument — that is a bonus. A heap is needed for two things.

First: the best ten. You want to show the ten highest-rated books out of 100,000. The obvious way is to sort and take the first ten. Step 5 measures what "obvious" costs.

Second: it is Dijkstra's queue. In lessons 14 and 15 you will search a graph for paths, and at every step you have to ask "which unvisited node is nearest?" That question is what a heap exists for. transit — the Vilnius journey planner — revolves around exactly this one question, and step 8 shows what answering it badly costs.