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 7 measures it, and step 8 shows why three answers can differ and all three be right.

The lesson climbs in steps

You do not start from empty panic("not implemented") bodies. The lesson climbs them in order, as lesson 7 did:

1. Watch. Seven pushes and seven pops, every step in a table. You write nothing.
2. Fill the holes. Pop arrives with its loop written. Two places are missing.
3. Write it yourself. TopKHeap, Height and IsHeap — empty skeletons.
4. Measure. Then the numbers arrive.

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 6 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 9 shows what answering it badly costs.