Heaps & Priority Queues

Code

heap.go — the skeleton

Create heap.go. The usual skeleton; the bodies are yours.

Worth noting:

Peek must be O(1). No loop, no comparison — a[0]. If you are searching, re-read the heap property.
Pop moves the last element of the array to the root, not a child. Step 2's gotcha.
Push compares against the parent; Pop against both children. So Pop does roughly twice the comparisons per level that Push does.
Swaps are not comparisons. c.Hit() fires only when two ratings are compared; swaps accumulate in Swaps. Step 6 rests on that distinction.
NewMinHeap takes a capacity hint and must use it (make([]Item, 0, capacity)). That is what makes the whole structure one allocation — the number step 6 sets against 20,020.

`TopKHeap` — where the thinking is

TopKHeap uses a min-heap of the k best items, and that is the whole trick.

The heap holds the k best seen so far. Its minimum is the weakest of those k. A new record only has to beat that one:

if the heap holds fewer than k: Push and continue
worst ← Peek()
c.Hit()
if the new one ≤ worst: skip        // cannot displace the weakest of the k best
Pop(); Push(the new one)

For most records that is one comparison and done. Which is why the cost is O(n log k) rather than O(n log n).

A min-heap for "the best" looks inverted, and it should: you keep the best and watch the worst of them, because that is the one that leaves first.

At the end the heap is drained and the result reversed — Pop gives the smallest first, and you want the best first.

heap.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithm is in step 2; heap_test.go
// decides whether you got it right.
//
// Every comparison between two RATINGS goes through c.Hit(). Swaps are counted
// separately in Swaps — they are not comparisons, and step 6 is about work the
// counter cannot see.

// MinHeap is a binary heap keyed on Rating, and it is A TREE STORED IN AN ARRAY.
//
// There are no pointers here. For the node at index i:
//
//	parent   (i-1)/2
//	children 2i+1 and 2i+2
//
// Lessons 11 and 12 spent 88 and 96 bytes per node on pointers scattered across
// the heap. This spends 0, in one contiguous slice — which is why its constant
// is small.
type MinHeap struct {
	a     []Item
	Swaps int
}

// NewMinHeap takes a capacity hint. Pre-sizing the slice is why the whole
// structure can be ONE allocation — step 6 measures that against the 20,020 the
// standard library needs for the same work.
func NewMinHeap(capacity int) *MinHeap { panic("not implemented") }

func (h *MinHeap) Len() int { panic("not implemented") }

// Peek returns the minimum without removing it. This must be O(1) — no loop, no
// comparison. If you find yourself searching, re-read the heap property.
func (h *MinHeap) Peek() (Item, bool) { panic("not implemented") }

// Push appends at the end and sifts UP until the parent is no larger.
func (h *MinHeap) Push(it Item, c *metrics.Counter) { panic("not implemented") }

// Pop removes and returns the minimum.
//
// The LAST element of the array moves to the root and sinks. Promoting a child
// instead leaves a hole and breaks the shape — see step 2's gotcha.
func (h *MinHeap) Pop(c *metrics.Counter) (Item, bool) { panic("not implemented") }

// Height is the depth of the array-tree: floor(log2(n)) + 1.
//
// No traversal is needed — the shape is implied by the length alone. Lesson 11
// had to walk the whole tree for this; here there is nothing to walk.
func (h *MinHeap) Height() int { panic("not implemented") }

// IsHeap checks the invariant everywhere: no parent larger than its child. The
// test calls it after every single Push, so keep it simple and correct rather
// than clever.
func (h *MinHeap) IsHeap() bool { panic("not implemented") }

// TopKHeap returns the k highest-rated items, best first, using a MIN-heap of
// size k.
//
// The trick that makes it O(n log k): the heap holds the k best seen so far, and
// its MINIMUM is the weakest of them. A new item only has to beat that one — so
// most items cost a single comparison and are discarded.
//
// It must NOT sort the input, and it must not hold more than k items at a time.
func TopKHeap(items []Item, k int, c *metrics.Counter) []Item {
	panic("not implemented")
}

heap.go — the skeleton

TopKHeap — where the thinking is

`TopKHeap` — where the thinking is