Heaps & Priority Queues

The Heap Property

A min-heap is a binary tree in which every parent is less than or equal to its children. The smallest element is therefore always at the root. Nothing else is ordered: siblings can appear in any order, and a heap is not sorted.

Complete Trees in Arrays

A binary heap is also a complete tree: every level is full except possibly the last, which fills from left to right. A complete tree has no gaps, so it can be stored level by level in a slice with no pointers at all. Parent and child positions are computed with arithmetic.

The same heap as a tree and as a slice. The node at index 1 (blue) has its children at indices 2·1+1 = 3 and 2·1+2 = 4 (orange).

// Index arithmetic for a heap stored in a slice (0-based).
func parent(i int) int { return (i - 1) / 2 }
func left(i int) int   { return 2*i + 1 }
func right(i int) int  { return 2*i + 2 }

Min-Heaps and Max-Heaps

A max-heap reverses the rule: every parent is greater than or equal to its children. Rather than writing two implementations, make the ordering a parameter. With a less(a, b) function, a < b produces a min-heap, a > b a max-heap, and a comparison on a struct field produces a priority queue of tasks.

Heap Operations

Every operation changes the heap in one place and then repairs the heap property along a single root-to-leaf path. The height of a complete tree is about log₂ n, so the repairs cost O(log n). Full implementation with heapsort and randomized verification: 27_binary_heap.go.

Push and Sift Up

Append the new element at the end — the only position that keeps the tree complete — then swap it with its parent while it is smaller. It rises at most to the root.

func (h *Heap[T]) Push(v T) {
	h.data = append(h.data, v)
	i := len(h.data) - 1
	for i > 0 {
		p := (i - 1) / 2
		if !h.less(h.data[i], h.data[p]) {
			break // parent is not larger: the heap property holds
		}
		h.data[i], h.data[p] = h.data[p], h.data[i]
		i = p
	}
}

Pop and Sift Down

The root is the answer. Remove it by moving the last element into the root — again keeping the tree complete — and sink that element: swap it with its smaller child while that child is smaller than it. Swapping with the larger child would place a larger value above a smaller one and break the property.

func (h *Heap[T]) siftDown(i int) {
	n := len(h.data)
	for {
		smallest := i
		l, r := 2*i+1, 2*i+2
		if l < n && h.less(h.data[l], h.data[smallest]) {
			smallest = l
		}
		if r < n && h.less(h.data[r], h.data[smallest]) {
			smallest = r
		}
		if smallest == i {
			return // both children are larger or absent
		}
		h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
		i = smallest
	}
}

Heapify in O(n)

Building a heap by pushing n elements costs O(n log n). Building it in place is faster: leaves are already valid one-element heaps, so sift down every internal node, from the last parent (n/2 − 1) back to the root. The total is O(n) because work is proportional to how far each node can sink: half of the nodes are leaves and sink zero levels, a quarter sink at most one, an eighth at most two, and so on. The sum n/4·1 + n/8·2 + n/16·3 + … is less than n.

Heapsort

Heapify the slice as a max-heap, then repeatedly swap the root (the current maximum) to the end of the unsorted region and sift the new root down in the shrunken heap. Heapsort runs in O(n log n) in the worst case with O(1) extra space, but it is not stable and its memory access pattern is less cache-friendly than quicksort's; Phase 3 compares the sorting algorithms.

container/heap

The standard library provides the heap algorithms, not a heap type. You define the storage and ordering by implementing heap.Interface; the package's functions keep the heap property.

heap.Interface

heap.Interface is sort.Interface (Len, Less, Swap) plus Push and Pop. Your Push and Pop only append to and remove from the end of the slice; heap.Push and heap.Pop call them and do the sifting.

// IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
	old := *h
	x := old[len(old)-1] // heap.Pop already moved the minimum here
	*h = old[:len(old)-1]
	return x
}

// usage: always through the package functions
h := &IntHeap{5, 2, 8}
heap.Init(h)          // O(n) heapify
heap.Push(h, 1)       // O(log n)
m := heap.Pop(h).(int) // 1, O(log n)

Updating Priorities with heap.Fix

Schedulers need to change the priority of an item already in the queue. If each item stores its current index — updated in Swap — you can change its priority and call heap.Fix(h, item.index), which sifts it up or down in O(log n). Without the stored index you would need an O(n) search. Dijkstra's algorithm uses the same "decrease key" operation.

Priority Queue Patterns

Four patterns cover most uses of a priority queue. All of them, plus the scheduler with heap.Fix: 28_priority_queue_patterns.go.

Top-k

To keep the k largest values of a large stream, maintain a min-heap of size k. Its root is the smallest of the current top k; a new value larger than the root replaces it. The cost is O(n log k) time and O(k) memory — the full stream never needs to be stored or sorted. Using a max-heap of everything would cost O(n) memory instead.

k-Way Merge

To merge k sorted inputs, put the first element of each into a min-heap. Repeatedly pop the smallest and push the next element from the same input. The heap never holds more than k elements, so merging N total elements costs O(N log k). Databases and external sorting tools merge sorted runs from disk this way.

Running Median

To report the median after every insertion, keep the lower half of the values in a max-heap and the upper half in a min-heap, with sizes differing by at most one. The median is at the top of one heap or the average of both tops: O(log n) per insertion, O(1) per query.

func (m *MedianFinder) Add(v int) {
	if m.low.Len() == 0 || v <= m.low.IntHeap[0] {
		heap.Push(&m.low, v) // belongs to the lower half
	} else {
		heap.Push(&m.high, v)
	}
	// rebalance: len(low) == len(high) or len(high)+1
	if m.low.Len() > m.high.Len()+1 {
		heap.Push(&m.high, heap.Pop(&m.low))
	} else if m.high.Len() > m.low.Len() {
		heap.Push(&m.low, heap.Pop(&m.high))
	}
}

Common Pitfalls

Most heap bugs come from confusing a heap with a sorted list, or from bypassing the package functions.

Calling h.Push Instead of heap.Push

Your type's Push method only appends; it does not sift. Calling h.Push(x) directly compiles and runs, but silently breaks the heap property. Always call heap.Push(h, x) and heap.Pop(h).

Treating the Heap as Sorted

Only the root is guaranteed. Iterating over the heap's slice does not yield sorted order, and h[1] is not necessarily the second smallest element. To read elements in order, pop them.

Searching a Heap

Finding an arbitrary element in a heap is O(n). If you need to update or remove specific items, keep their indices (as with heap.Fix) or a map from item to index.

Practice Lab

For each exercise, decide what the heap stores and what its root means.

Run the Demos

1. In 27_binary_heap.go, change siftDown to swap with the larger child and run the randomized heapsort check.
2. In 28_priority_queue_patterns.go, change a task's priority without calling heap.Fix. In what order do the tasks come out?

Exercises

1. K closest points. Return the k points closest to the origin using a max-heap of size k keyed by squared distance.
2. Task scheduler. Given tasks with durations and k workers, compute when all tasks finish, using a min-heap of worker finish times.
3. Meeting rooms. Find the minimum number of rooms for a list of meetings: sort by start time and keep a min-heap of end times.
4. Generic d-ary heap. Generalize Heap[T] so each node has d children. How do the index formulas change, and how does d affect push and pop costs?

Phase 2 is complete. Continue with Searching, the first lesson of Phase 3.