A heap keeps the smallest value at the front without keeping everything sorted. It is a slice that pretends to be a tree, and it is what makes a priority queue fast.
The key idea
A tree with no pointers in it
- The array is the tree, read top to bottom and left to right.
- The children of
isit at2i+1and2i+2, and the parent at(i-1)/2.
Push and pop each restore that rule by swapping one value along a single branch.
The rule
Partially ordered tree, held in an array
Every parent is smaller than its children, so the smallest value is always at index 0.
- Push: put the value at the end and swap it up while it beats its parent.
- Pop: take index 0, move the last value into the gap, and swap it back down.
The same values shown two ways: the tree the heap behaves like, and the slice it actually is. Push a value and watch it climb; pop and watch the last value drop to the top and sink.
Purpose
Keep a collection where the smallest value is always ready to come out first.
Input
Values pushed one at a time into a []int.
Output
The smallest value still held, handed back by Pop.
Constraints
- Only the smallest is reachable. Everything else is partly ordered rather than sorted.
- The array has no gaps, so the tree stays balanced without any work.
- A max-heap is the same code with the comparison flipped, or
container/heapwith a differentLess.
How a heap is laid out
A slice, plus the rule that every parent is smaller than its children.
No pointers and no nodes. The tree exists only in the index arithmetic: multiply to go down, halve to go up.
// A heap is a slice read as a tree.
type Heap []int
// Index i's children are at 2i+1 and 2i+2.
// Index i's parent is at (i-1)/2.Walk through it
Sequencing
Two steps to add a value.
It goes on the end, which is the only spot that keeps the tree complete. That is almost certainly the wrong place, and the next part fixes it.
*h = append(*h, v) // new value goes on the end
i := len(*h) - 1 // and that is where it startsSelection
The decision, made against the parent.
If the parent is already smaller, the rule holds and there is nothing left to do. Otherwise the two swap and the value keeps climbing.
parent := (i - 1) / 2
if (*h)[parent] <= (*h)[i] {
break // parent is smaller, so we are done
}Iteration
The same comparison, one level higher each time.
Only the path from the value to the root is touched. Everything else in the heap is left alone, which is why this is cheap.
for i > 0 {
// ... compare with parent, swap if smaller
i = parent // climb one level and check again
}What comes out
The smallest value, always at index 0.
Removing it leaves a hole, so the last value is moved into it and sinks down, swapping with its smaller child until the rule holds again.
func (h *Heap) Pop() int {
old := *h
root := old[0] // the smallest value
last := len(old) - 1
old[0] = old[last] // move the end to the top
*h = old[:last]
// ... then sink it back down
return root
}The whole program main.go Show
package main
import "fmt"
// A heap is a slice read as a tree: index i's children are at 2i+1 and 2i+2,
// and its parent is at (i-1)/2.
type Heap []int
func (h *Heap) Push(v int) {
*h = append(*h, v) // new value goes on the end
i := len(*h) - 1 // and that is where it starts
for i > 0 {
parent := (i - 1) / 2
if (*h)[parent] <= (*h)[i] {
break // parent is smaller, so we are done
}
(*h)[parent], (*h)[i] = (*h)[i], (*h)[parent]
i = parent // climb one level and check again
}
}
func (h *Heap) Pop() int {
old := *h
root := old[0] // the smallest value
last := len(old) - 1
old[0] = old[last] // move the end to the top
*h = old[:last]
// Then sink it back down until both children are larger.
i, n := 0, len(*h)
for {
left, right, small := 2*i+1, 2*i+2, i
if left < n && (*h)[left] < (*h)[small] {
small = left
}
if right < n && (*h)[right] < (*h)[small] {
small = right
}
if small == i {
break
}
(*h)[i], (*h)[small] = (*h)[small], (*h)[i]
i = small
}
return root
}
func main() {
var h Heap
for _, v := range []int{5, 3, 8, 1, 9, 2} {
h.Push(v)
}
fmt.Println("heap array:", h)
fmt.Print("pops:")
for len(h) > 0 {
fmt.Print(" ", h.Pop())
}
fmt.Println()
}Six values pushed in a jumbled order, then popped. They come out sorted even though the array never was.
$ go run heap.go
heap array: [1 3 2 5 9 8]
pops: 1 2 3 5 8 9When it stops
Both loops move i along one path of the tree, and a path is at most log₂(n) steps long.
Climbing halves the index until it hits 0. Sinking at least doubles it until it runs past the end. Neither can loop forever.
// Bubbling up: i halves every pass, so it reaches 0.
i = (i - 1) / 2
// Sinking down: i at least doubles, so it runs off the end.
i = 2*i + 1What it costs
| Operation | Time | Why |
|---|---|---|
| Peek the smallest | O(1) | It is always at index 0. |
| Push | O(log n) | One climb along a single path to the root. |
| Pop | O(log n) | One sink along a single path to a leaf. |
| Build from n values | O(n) | Heapifying in place beats n pushes, which would be O(n log n). |
| Space | O(n) | The slice itself. There is no per-node overhead. |
Using container/heap instead
container/heap is the version to reach for in real code. It implements the bubbling; you implement five methods that say how to compare and store.
Less is where the ordering lives. Flip the comparison and the same code gives you a max-heap.
// The standard library does the bubbling for you. You supply
// the ordering and the storage.
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
v := old[len(old)-1]
*h = old[:len(old)-1]
return v
}
h := &IntHeap{5, 3, 8}
heap.Init(h)
heap.Push(h, 1)
fmt.Println(heap.Pop(h)) // 1