100,000 books. You need the ten highest-rated.

Guess before you read on

The obvious way: sort by Rating and take the first ten. Lesson 9 sorts 100,000 records in milliseconds, so it does not even look expensive.

Can the best ten be found WITHOUT sorting? And if so, what is the smallest number of comparisons it would take?

Write the number down.

The measurement

$ algo top -in s100k.jsonl -k 10
n = 100000, k = 10

                            comparisons         time       per item
  heap of size k                 100251      1.002ms           1.00
  sort.Slice, take k             841189      6.014ms           8.41

  ratio: 8.4x fewer comparisons
  same k ratings? true

1.00 comparison per record.

Not 8.41. Not log2(100000) = 16.6. One. The heap looks at every record exactly once and throws almost all of them away immediately.

And the last line says the answers agree: same k ratings? true.

Why one is enough

The heap holds the ten best seen so far. Its minimum is the weakest of those ten.

A new record arrives. One comparison against that weakest:

• if it is worse — it cannot belong in the best ten, because it is worse than ten records already held. Discarded. One comparison, done;
• if it is better — the weakest leaves, the new one enters. That is a Pop plus a Push, about 2 · log2(10) ≈ 7 comparisons.

On random data the second case gets rarer and rarer: to break into the top ten of 100,000 you have to beat the best ten seen so far. Which is why the average settles on one.

Sorting answers "what is the order of everything?" You needed an answer to "which ten are best?" The first question is harder, and you were about to pay for it.

Partial order is enough

A heap does not sort. Step 3's test insists on it.

It knows one thing — its minimum — and nothing else. Siblings are unordered between themselves, and deeper levels carry no order at all.

In lesson 10 the hash table gave up order completely and got O(1) for it. In lesson 11 the tree kept order entirely and paid O(log n). The heap stands between them:

structure	how much order	what it gets
hash table (10)	none	O(1) exact-key lookup
heap (13)	the minimum only	O(1) minimum, O(log n) to add or take
BST / AVL (11-12)	complete	ranges, neighbours, sorted output

Take exactly as much order as the question needs, and no more. That is the idea of this whole lesson, and the heap is its clearest example.

Where the limit is

The heap does not always win. Raise k:

$ for k in 1 10 100 1000 10000 100000; do algo top -in s100k.jsonl -k $k; done

       k       heap            sort
       1      99999          841189
      10     100251          841189
     100     105510          841189
    1000     180960          841189
   10000     878748          841189
  100000    3037870          841189

The turnover is between k = 1,000 and k = 10,000, around k ≈ n/10. At k = n the heap does 3.6× more work than the sort.

That is as it should be: O(n log k) is a win only while log k is well under log n. When k = n it is the same O(n log n) — with a worse constant, because every element goes through a separate Push and Pop.

TestTopKLosesWhenKApproachesN requires that to stay true.

And the clock agrees

$ go test -run XXX -bench 'TopK' -benchtime=20x -count=5

BenchmarkTopKHeap-32      20     680625 ns/op
BenchmarkTopKHeap-32      20     666920 ns/op
BenchmarkTopKHeap-32      20     700495 ns/op
BenchmarkTopKSort-32      20    6032965 ns/op
BenchmarkTopKSort-32      20    6152325 ns/op
BenchmarkTopKSort-32      20    6041960 ns/op

0.67–0.70 ms against 6.03–6.16 ms. 8.9×, and the ranges do not even touch.

Here the counter and the clock agree. In the next step they will not.