Always know the smallest (or largest) item. Priority queues, top-k, and container/heap.
A heap answers one question fast: what's the minimum right now? — while still allowing inserts and removals in O(log n). That's a priority queue, and it shows up in schedulers (run the most urgent job next), Dijkstra's shortest paths (Module 9), event simulations, top-k queries, and merging many sorted streams (which is how databases and log tools merge sorted files).
Heap property. In a min-heap every parent is ≤ its children, so the root is the minimum. Nothing is promised about left versus right — a heap is only partially ordered, which is why it's cheaper to maintain than a sorted list.
Stored in a slice. A heap is a complete binary tree (every level full except possibly the last, filled left to right), so it packs into an array with no pointers. For index i: parent (i-1)/2, children 2i+1 and 2i+2.
Sift up / sift down.
Both walk one path of height log n.
Heapify in O(n). Building a heap by n pushes costs O(n log n). Sifting down every non-leaf, from the last one back to the root, costs only O(n) — most nodes are near the bottom and barely move.
Heap sort. Heapify into a max-heap, then repeatedly swap the root to the end of the array and shrink. O(n log n), in place, not stable.
| Operation | Cost |
|---|---|
| Peek min | O(1) |
| Push / Pop | O(log n) |
| Build from n items | O(n) |
| Search for an arbitrary value | O(n) |
container/heap provides the algorithms; you provide the storage by implementing heap.Interface: Len, Less, Swap, plus Push(any) and Pop() any that just append to and remove from the end of your slice.heap.Push(h, x) and heap.Pop(h), not your methods. Your Push only appends; heap.Push appends and sifts. Calling h.Push(x) directly silently breaks the heap.Less for a max-heap. Or push negated values into a min-heap.heap.Fix(h, i) re-sifts after you change element i's priority — useful when you track each item's index.any, so you'll type-assert: heap.Pop(h).(int).type Task struct { Name string Priority int // lower runs first } type TaskQueue []Task func (q TaskQueue) Len() int { return len(q) } func (q TaskQueue) Less(i, j int) bool { return q[i].Priority < q[j].Priority } func (q TaskQueue) Swap(i, j int) { q[i], q[j] = q[j], q[i] } func (q *TaskQueue) Push(x any) { *q = append(*q, x.(Task)) } func (q *TaskQueue) Pop() any { old := *q t := old[len(old)-1] *q = old[:len(old)-1] return t } func runAll() { q := &TaskQueue{} heap.Push(q, Task{"backup", 3}) heap.Push(q, Task{"page on-call", 1}) heap.Push(q, Task{"rotate logs", 2}) for q.Len() > 0 { fmt.Println(heap.Pop(q).(Task).Name) // page on-call, rotate logs, backup } }
Part A builds a generic MinHeap[T cmp.Ordered] by hand — the tests check the heap property after every push and pop — plus O(n) Heapify and in-place HeapSort. Part B switches to container/heap for four problems; IntMinHeap and IntMaxHeap adapters are ready in types.go.
go test ./08-heaps/
You'll need to add import "container/heap" to exercises.go for Part B.
Everything below is also in the course download, in 08-heaps/. Work in exercises.go; the tests decide when you’re done.
// Package heaps is Module 8: binary heaps and priority queues. // // A binary heap is a complete binary tree stored in a slice — no pointers. // For the node at index i: // // parent = (i-1)/2 left = 2i+1 right = 2i+2 // // Part A builds a generic min-heap by hand. Part B switches to the standard // library's container/heap, which is what you'd reach for in real code. package heaps import "cmp" // MinHeap is a binary min-heap: data[0] is the smallest element, and every // parent is <= its children. type MinHeap[T cmp.Ordered] struct { data []T } // Len returns the number of elements. func (h *MinHeap[T]) Len() int { return len(h.data) } // --------------------------------------------------------------------------- // container/heap adapters. heap.Interface needs Len, Less, Swap, Push, Pop; // these two types are ready to use with heap.Push / heap.Pop / heap.Init. // IntMinHeap is a min-heap of ints for container/heap. type IntMinHeap []int func (h IntMinHeap) Len() int { return len(h) } func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] } func (h IntMinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntMinHeap) Push(x any) { *h = append(*h, x.(int)) } func (h *IntMinHeap) Pop() any { old := *h v := old[len(old)-1] *h = old[:len(old)-1] return v } // IntMaxHeap is a max-heap of ints for container/heap. type IntMaxHeap []int func (h IntMaxHeap) Len() int { return len(h) } func (h IntMaxHeap) Less(i, j int) bool { return h[i] > h[j] } func (h IntMaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntMaxHeap) Push(x any) { *h = append(*h, x.(int)) } func (h *IntMaxHeap) Pop() any { old := *h v := old[len(old)-1] *h = old[:len(old)-1] return v } // MedianFinder tracks the running median of a stream of ints. // lo is a max-heap holding the smaller half; hi is a min-heap holding the // larger half. Keep len(lo) == len(hi) or len(lo) == len(hi)+1. type MedianFinder struct { lo IntMaxHeap hi IntMinHeap }
//go:build !solutions package heaps import "cmp" // ============================================================ // Part A — build a min-heap by hand (see types.go for index math) // ============================================================ // Push adds v: append it at the end, then sift it up while it's smaller // than its parent. Target: O(log n). func (h *MinHeap[T]) Push(v T) { // TODO } // Peek returns the smallest element without removing it, or (zero, false). // Target: O(1). func (h *MinHeap[T]) Peek() (T, bool) { // TODO var zero T return zero, false } // Pop removes and returns the smallest element, or (zero, false): move the // last element to the root, shrink, then sift it down, always swapping with // the smaller child. Target: O(log n). func (h *MinHeap[T]) Pop() (T, bool) { // TODO var zero T return zero, false } // Heapify builds a heap from vals in O(n) — not n Pushes (that's // O(n log n)). Copy vals, then sift down every non-leaf node, starting from // the last one (index len/2 - 1) back to the root. Don't modify vals. func Heapify[T cmp.Ordered](vals []T) *MinHeap[T] { // TODO return &MinHeap[T]{} } // HeapSort sorts nums ascending in place with O(1) extra space: build a // MAX-heap inside nums, then repeatedly swap the root to the end of the // unsorted region and sift down. Target: O(n log n). func HeapSort(nums []int) { // TODO } // ============================================================ // Part B — priority-queue problems with container/heap // (import "container/heap"; IntMinHeap / IntMaxHeap are in types.go) // ============================================================ // KthLargest returns the k-th largest value (1 <= k <= len(nums)). // [3 2 1 5 6 4], k=2 -> 5. // Pattern: keep a min-heap of size k; its root is the answer. // Target: O(n log k). func KthLargest(nums []int, k int) int { // TODO return 0 } // MergeKSorted merges k ascending slices into one ascending slice. // Pattern: a heap of "cursors" (which list, which index, value). You'll // need your own heap.Interface type for the cursor struct. // Target: O(N log k), N = total elements. func MergeKSorted(lists [][]int) []int { // TODO return nil } // LastStoneWeight: each turn, smash the two heaviest stones. Equal stones // are both destroyed; otherwise the heavier one survives with weight a-b. // Return the last stone's weight, or 0 if none remain. // [2 7 4 1 8 1] -> 1. Use IntMaxHeap. Don't modify stones. func LastStoneWeight(stones []int) int { // TODO return 0 } // Add inserts n into the MedianFinder. Push into lo, move lo's max over to // hi, then if hi got bigger than lo move hi's min back. Target: O(log n). func (m *MedianFinder) Add(n int) { // TODO } // Median returns the median of everything added so far, or (0, false) if // nothing has been added. Even count -> average of the two middle values. // Target: O(1). func (m *MedianFinder) Median() (float64, bool) { // TODO return 0, false }
package heaps import ( "math/rand" "slices" "testing" ) func checkHeapProperty[T int | string](t *testing.T, data []T) { t.Helper() for i := 1; i < len(data); i++ { if p := (i - 1) / 2; data[p] > data[i] { t.Fatalf("heap property broken: data[%d]=%v > data[%d]=%v", p, data[p], i, data[i]) } } } func sortedCopy(s []int) []int { c := slices.Clone(s) slices.Sort(c) return c } func TestMinHeapPushPop(t *testing.T) { var h MinHeap[int] in := []int{5, 3, 8, 1, 9, 2, 7, 1} for _, v := range in { h.Push(v) checkHeapProperty(t, h.data) } if v, ok := h.Peek(); !ok || v != 1 { t.Fatalf("Peek() = (%d, %v), want (1, true)", v, ok) } want := sortedCopy(in) for _, w := range want { if v, ok := h.Pop(); !ok || v != w { t.Fatalf("Pop() = (%d, %v), want (%d, true)", v, ok, w) } checkHeapProperty(t, h.data) } if _, ok := h.Pop(); ok { t.Error("Pop() on empty heap should return ok=false") } } func TestMinHeapStrings(t *testing.T) { var h MinHeap[string] for _, s := range []string{"pear", "apple", "fig", "banana"} { h.Push(s) } var got []string for h.Len() > 0 { s, _ := h.Pop() got = append(got, s) if len(got) > 4 { break } } if want := []string{"apple", "banana", "fig", "pear"}; !slices.Equal(got, want) { t.Errorf("popped %v, want %v", got, want) } } func TestHeapify(t *testing.T) { r := rand.New(rand.NewSource(1)) vals := make([]int, 200) for i := range vals { vals[i] = r.Intn(1000) } orig := slices.Clone(vals) h := Heapify(vals) if !slices.Equal(vals, orig) { t.Fatal("Heapify modified its input slice") } if h.Len() != len(vals) { t.Fatalf("Len() = %d, want %d", h.Len(), len(vals)) } checkHeapProperty(t, h.data) slices.Sort(orig) for _, w := range orig { if v, _ := h.Pop(); v != w { t.Fatalf("Pop() after Heapify = %d, want %d", v, w) } } } func TestHeapSort(t *testing.T) { r := rand.New(rand.NewSource(2)) for _, n := range []int{0, 1, 2, 5, 100} { nums := make([]int, n) for i := range nums { nums[i] = r.Intn(50) - 25 } want := sortedCopy(nums) HeapSort(nums) if !slices.Equal(nums, want) { t.Errorf("HeapSort (n=%d) = %v, want %v", n, nums, want) } } } func TestKthLargest(t *testing.T) { for _, tc := range []struct { nums []int k, want int }{ {[]int{3, 2, 1, 5, 6, 4}, 2, 5}, {[]int{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4, 4}, {[]int{7}, 1, 7}, {[]int{-1, -5, -3}, 3, -5}, } { if got := KthLargest(tc.nums, tc.k); got != tc.want { t.Errorf("KthLargest(%v, %d) = %d, want %d", tc.nums, tc.k, got, tc.want) } } } func TestMergeKSorted(t *testing.T) { for _, tc := range []struct { lists [][]int want []int }{ {[][]int{{1, 4, 5}, {1, 3, 4}, {2, 6}}, []int{1, 1, 2, 3, 4, 4, 5, 6}}, {[][]int{{}, {0}, {}}, []int{0}}, {[][]int{{-2, 10}, {-5, -1, 20}}, []int{-5, -2, -1, 10, 20}}, } { if got := MergeKSorted(tc.lists); !slices.Equal(got, tc.want) { t.Errorf("MergeKSorted(%v) = %v, want %v", tc.lists, got, tc.want) } } } func TestLastStoneWeight(t *testing.T) { for _, tc := range []struct { in []int want int }{ {[]int{2, 7, 4, 1, 8, 1}, 1}, {[]int{1}, 1}, {[]int{3, 3}, 0}, {[]int{10, 4, 2, 10}, 2}, } { orig := slices.Clone(tc.in) if got := LastStoneWeight(tc.in); got != tc.want { t.Errorf("LastStoneWeight(%v) = %d, want %d", orig, got, tc.want) } if !slices.Equal(tc.in, orig) { t.Errorf("LastStoneWeight modified its input") } } } func TestMedianFinder(t *testing.T) { var m MedianFinder if _, ok := m.Median(); ok { t.Fatal("Median() with no data should return ok=false") } for _, step := range []struct { add int want float64 }{ {5, 5}, {15, 10}, {1, 5}, {3, 4}, {8, 5}, {7, 6}, {9, 7}, {10, 7.5}, } { m.Add(step.add) if got, ok := m.Median(); !ok || got != step.want { t.Fatalf("after Add(%d), Median() = (%v, %v), want (%v, true)", step.add, got, ok, step.want) } } }
Try not to open solution.go until your tests pass, or until you’ve been stuck for a solid half hour. Then compare: different-but-correct is fine; notice where the reference is simpler. go test -tags solutions ./08-heaps/ runs the same tests against it.
solutions · 183 lines›//go:build solutions package heaps import ( "cmp" "container/heap" ) // ---------- MinHeap ---------- func (h *MinHeap[T]) siftUp(i int) { for i > 0 { p := (i - 1) / 2 if h.data[p] <= h.data[i] { return } h.data[p], h.data[i] = h.data[i], h.data[p] i = p } } func (h *MinHeap[T]) siftDown(i int) { n := len(h.data) for { smallest := i if l := 2*i + 1; l < n && h.data[l] < h.data[smallest] { smallest = l } if r := 2*i + 2; r < n && h.data[r] < h.data[smallest] { smallest = r } if smallest == i { return } h.data[i], h.data[smallest] = h.data[smallest], h.data[i] i = smallest } } func (h *MinHeap[T]) Push(v T) { h.data = append(h.data, v) h.siftUp(len(h.data) - 1) } func (h *MinHeap[T]) Peek() (T, bool) { var zero T if len(h.data) == 0 { return zero, false } return h.data[0], true } func (h *MinHeap[T]) Pop() (T, bool) { var zero T n := len(h.data) if n == 0 { return zero, false } top := h.data[0] h.data[0] = h.data[n-1] h.data = h.data[:n-1] h.siftDown(0) return top, true } func Heapify[T cmp.Ordered](vals []T) *MinHeap[T] { h := &MinHeap[T]{data: append([]T(nil), vals...)} for i := len(h.data)/2 - 1; i >= 0; i-- { h.siftDown(i) } return h } func HeapSort(nums []int) { // Build a max-heap in place, then repeatedly move the max to the end. n := len(nums) down := func(i, end int) { for { largest := i if l := 2*i + 1; l < end && nums[l] > nums[largest] { largest = l } if r := 2*i + 2; r < end && nums[r] > nums[largest] { largest = r } if largest == i { return } nums[i], nums[largest] = nums[largest], nums[i] i = largest } } for i := n/2 - 1; i >= 0; i-- { down(i, n) } for end := n - 1; end > 0; end-- { nums[0], nums[end] = nums[end], nums[0] down(0, end) } } // ---------- container/heap problems ---------- func KthLargest(nums []int, k int) int { h := &IntMinHeap{} for _, v := range nums { heap.Push(h, v) if h.Len() > k { heap.Pop(h) } } return (*h)[0] } type cursor struct{ list, idx, val int } type cursorHeap []cursor func (h cursorHeap) Len() int { return len(h) } func (h cursorHeap) Less(i, j int) bool { return h[i].val < h[j].val } func (h cursorHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *cursorHeap) Push(x any) { *h = append(*h, x.(cursor)) } func (h *cursorHeap) Pop() any { old := *h v := old[len(old)-1] *h = old[:len(old)-1] return v } func MergeKSorted(lists [][]int) []int { h := &cursorHeap{} total := 0 for i, l := range lists { total += len(l) if len(l) > 0 { *h = append(*h, cursor{i, 0, l[0]}) } } heap.Init(h) out := make([]int, 0, total) for h.Len() > 0 { c := heap.Pop(h).(cursor) out = append(out, c.val) if next := c.idx + 1; next < len(lists[c.list]) { heap.Push(h, cursor{c.list, next, lists[c.list][next]}) } } return out } func LastStoneWeight(stones []int) int { h := IntMaxHeap(append([]int(nil), stones...)) heap.Init(&h) for h.Len() > 1 { a := heap.Pop(&h).(int) b := heap.Pop(&h).(int) if a != b { heap.Push(&h, a-b) } } if h.Len() == 0 { return 0 } return h[0] } func (m *MedianFinder) Add(n int) { heap.Push(&m.lo, n) heap.Push(&m.hi, heap.Pop(&m.lo)) // largest of the small half moves up if m.hi.Len() > m.lo.Len() { heap.Push(&m.lo, heap.Pop(&m.hi)) } } func (m *MedianFinder) Median() (float64, bool) { if m.lo.Len() == 0 { return 0, false } if m.lo.Len() > m.hi.Len() { return float64(m.lo[0]), true } return float64(m.lo[0]+m.hi[0]) / 2, true }
Update to a priority queue that tracks each item's index, using heap.Fix.Four questions. Answer each one in your head — or out loud — before you open the answer.
In an array-backed binary heap, what are the children of index 4?
C — Children are 2i+1 and 2i+2: 9 and 10. The parent of i is (i-1)/2.
You implemented heap.Interface and then call h.Push(x) instead of heap.Push(h, x). What happens?
C — Your Push only appends. The package function heap.Push appends via your method and then restores order.
To keep the k LARGEST values from a stream, which heap do you use?
B — The min-heap's root is the smallest of your current top k — the one to evict when something bigger arrives. O(n log k).
Why is bottom-up Heapify O(n) and not O(n log n)?
B — Half the nodes are leaves (no work), a quarter sift at most 1 level, an eighth at most 2… that series sums to O(n).
Commit your work before you move on to module 9, so git log shows your own progress through the course.