Five tasks.

---

1. Heapsort

Draining a heap gives ascending order, which is a sorting algorithm. Write heapSort(items []Item, c *metrics.Counter) []Item: build a heap, then Pop everything into a slice.

It is O(n log n), in place if you want it to be, and needs no extra memory. So how does it compare with lessons 7 to 9?

n=100000: heapsort 3002497 comparisons, sort.Slice 813236 (3.69x)

3.69× more comparisons than sort.Slice. Explain where they come from — count how many comparisons one Pop does per level and compare with one merge step in lesson 8.

Then answer: heapsort is O(n log n) and needs no extra memory, which merge sort does. Why does nobody use it as their default sort anyway?

---

2. Build the heap the other way

There are two ways to turn n items into a heap: n calls to Push, or place them all in the array and sift each one down, starting at n/2 - 1. The second is called heapify.

The textbook says n Pushes is O(n log n) and heapify is O(n). Measure it:

random data
n=  1000: 1000 Pushes cost     2234 cmps (2.23/item); heapify     1867 (1.87/item)
n=100000: 100000 Pushes cost 223155 cmps (2.23/item); heapify   187550 (1.88/item)

Both are linear, and heapify wins by only 16%. The textbook's log n has gone missing.

Now feed it ordered input:

n=100000: Push ascending 99999 (1.00/item) · Push descending 1468946 (14.69/item) · heapify 199978 (2.00/item)

There it is. Explain all three columns: why ascending input is Push's best case for a min-heap, why descending is its worst, and why heapify does not care.

Then say which of the three numbers the O(n log n) in the textbook refers to, and why random data landed so close to the best case.

---

3. A max-heap without a second implementation

algo top wants the highest ratings and you built a min-heap. There are three ways to get a max-heap:

• copy heap.go and flip every < to >;
• store -Rating and negate on the way out;
• take a comparison function as a field on the struct.

Implement one. Then argue for or against each of the other two — including what the third one costs, given what step 6 measured. (A func field is not an interface. Does that matter? Measure it.)

---

4. Boxing or dispatch?

Step 6 named two suspects and did not separate them. Separate them.

Write a third heap: container/heap again, but over []*Item instead of []Item. A pointer is pointer-shaped, so it fits inside an interface value and is not copied to the heap — you get the dispatch without the boxing.

BenchmarkHeapMine-32          20   1152790 ns/op    565248 B/op        1 allocs/op
BenchmarkHeapStdlibPtr-32     20   1158620 ns/op     81944 B/op        2 allocs/op
BenchmarkHeapStdlib-32        20   1932750 ns/op   3934116 B/op    20020 allocs/op

With pointers, container/heap ties the hand-written heap. Every bit of the 1.66× was boxing; the dispatch cost nothing measurable.

Explain why the dispatch turned out to be free — the call site is monomorphic and the branch is perfectly predicted. Then answer the question that matters: does this mean container/heap is fine after all? What did the pointer version cost you that the value version did not? (Look at where the Items now live, and at what lesson 11 measured about scattered memory.)

---

5. The crossover, precisely

Step 5 put the top-k crossover between k = 1,000 and k = 10,000 at n = 100,000.

Find it exactly, by bisection. Then repeat at n = 10,000 and n = 1,000,000.

Is the crossover a fixed k, a fixed ratio k/n, or something else? State a rule for when to use the heap and when to sort, and show the measurement it rests on.