Heaps & Priority Queues

The 30-second version

Picture the triage desk of a hospital emergency room. Patients arrive all day. Each one gets an urgency score: 1 for a heart attack, 5 for a sprained ankle. Whenever a doctor is free, the desk must answer one question: who is the most urgent person waiting right now?

A list of "things to do, most important first" that keeps changing is called a Priority queuePriority queueA queue that hands out the most important item first instead of the oldest. Usually built on a heap, so adding and removing are fast even with many items.. A normal queueQueue (data structure)A first-in, first-out line: you add at the back and remove from the front, like people waiting at a checkout. serves the oldest item first; a priority queue serves the most important one first. A heap is the usual way to build one. The terms are often used as if they were the same thing.

Why not just use a list?

The triage desk could keep its patients in a simple ArrayArrayItems stored one after another in a single block of memory, so item i is found by simple arithmetic in O(1). Go has fixed arrays and growable slices; JS arrays are growable.. There are two obvious ways, and each one is slow at one of the two jobs. In the table, n is the number of people waiting, and log₂ nLogarithm (log₂ n)How many times you can halve n before reaching 1. log₂ 8 = 3, log₂ 1,000 ≈ 10, log₂ 1,000,000 ≈ 20. It grows very slowly: a thousand times more data adds only about 10. is how many times you can halve n before reaching 1. It grows very slowly: log₂ 1,000 is about 10, and log₂ of a million is only about 20.

With 1,000 people waiting, "n steps" means about 1,000 steps per patient; log₂ n means about 10.

Run the race yourself. All three approaches handle exactly the same patients. Change the size of the waiting room and watch the bars:

What a heap gives you

That's all. A heap can't quickly search for an arbitrary item, and it doesn't keep everything sorted. It only keeps the one promise that matters to the triage desk, and that's why it's so cheap.

You'll find heaps wherever "what's next?" is asked over and over. Timers ask which deadline is soonest? (§10). Job schedulers ask which job has the highest priority? Analytics asks what are the 10 slowest requests out of a billion? (§08). Maps apps ask which unvisited place is closest? (§10). The next sections build one from scratch, then put it to work.

A tree hiding in an array

The tree you imagine

A TreeTree (data structure)Data shaped like an upside-down tree: one root node, each node has zero or more children, and nothing loops back. Nodes with no children are called leaves. Folders and files, HTML elements and React components are trees. here is a family-tree-shaped drawing of the data. Each item is a nodeNode (in a tree)One box in the tree: it holds a value plus links (pointers) to its children. A folder, an HTML element or one entry of a BST is a node.. The one at the top is the root, nodes directly below a node are its children, and nodes with no children are leaves. In a binary tree every node has at most two children.

A Binary heapBinary heapA tree where every parent is smaller than or equal to its children (or bigger, for a max-heap), packed level by level into an array. The smallest item is always at index 0. adds just one rule, the Heap propertyHeap propertyThe one rule a heap keeps: every parent is ≤ its children (min-heap) or ≥ them (max-heap). It says nothing about siblings, so a heap is only “a little bit sorted”.:

Every parent is smaller than or equal to each of its children.

Follow any path from the root downward and the numbers only grow. So the smallest number of all must be at the root. That's the whole trick: the answer to "what's most urgent?" is always sitting at the top.

Flip the rule ("every parent is bigger than or equal to its children") and you get a max-heap, with the biggest item on top. The code is identical except for one comparison. That's a Min-heap / max-heapMin-heap / max-heapA min-heap keeps the smallest item on top; a max-heap keeps the biggest on top. Same code, with the comparison flipped. pair; this page uses min-heaps unless it says otherwise.

The shape rule: no gaps

A heap also keeps its tree complete: every level is completely full before the next level starts, and the bottom level fills from left to right. It's a Complete binary treeComplete binary treeA binary tree where every level is full except maybe the last, and the last level fills from left to right with no gaps. That's what lets a heap live in an array with no empty slots.. Like seats in a theatre that fills row by row, left to right, there's never an empty seat in the middle.

Because of that shape, a heap with n items is as flat as a tree can be. Its HeightHeight (of a tree)The number of steps from the root down to the deepest leaf. A complete binary tree with n items has height ⌊log₂ n⌋ (log₂ n rounded down): 19 for a million items, which have 20 levels. (the number of steps from the root to the bottom) is about log₂ nLogarithm (log₂ n)How many times you can halve n before reaching 1. log₂ 8 = 3, log₂ 1,000 ≈ 10, log₂ 1,000,000 ≈ 20. It grows very slowly: a thousand times more data adds only about 10.:

Remember this table: every heap operation walks one path from top to bottom (or bottom to top), so it costs at most about one step per level.

The array you actually store

Number the nodes level by level, left to right: root = 0, its two children = 1 and 2, their children = 3, 4, 5, 6, and so on. Now put each node in an array at its number. Because the tree has no gaps, the array has no gaps either, and you can find relatives with simple arithmetic:

Try it below. Pick any node, in either view, and check the formulas against the picture:

No node stores pointers to its children. The positions are the links. That makes a heap small (just the values, nothing else) and fast: the items sit next to each other in memory, which the CPU loves (more in §11 and in CPU caches).

push and pop: sift up, sift down

Both operations follow the same two-step plan:

1. Keep the shape. Only ever add or remove at the end of the array, so the tree never gets a gap.
2. Repair the order. That step can put one item in the wrong place. Walk it up or down, swapping with a neighbour, until every parent is ≤ its children again.

push: add at the end, then sift up

Say the heap holds [3, 8, 12, 17, 25, 42, 63] and you push 5. Here's that heap as a tree; the small numbers are the array indexes:

1. Put 5 in the next free slot: index 7, a child of index 3 (value 17).
2. Compare with the parent: 5 is less than 17, so they're in the wrong order. Swap. 5 is now at index 3.
3. Compare with the new parent, index 1 (value 8): 5 is less than 8. Swap. 5 is at index 1.
4. Compare with the root (value 3): 5 isn't less than 3. Stop.

That climb is called Sift upSift upFixing a heap after adding an item at the end: while the item is smaller than its parent (min-heap), swap them. It climbs at most one path to the root. Also called bubble up, percolate up or siftUp.. A new item can only be in the wrong place relative to the nodes above it, so only that one path needs checking.

pop: take the root, move the last item up, sift down

The answer to pop is always the root. The hard part is filling the hole it leaves without making a gap:

1. Remember the root: that's what you'll return.
2. Move the last item of the array into the root's slot and shrink the array by one. The shape is fine again; the order probably isn't, because a big number is now on top.
3. Compare it with both children and swap it with the smaller one. (Swapping with the smaller child is what keeps the rule: the child that moves up must be ≤ its new sibling.)
4. Repeat until it is ≤ both of its children, or has no children.

That sinking is called Sift downSift downFixing a heap when the item at some position is too big for its spot (min-heap): swap it with its smaller child until it's ≤ both children or has none. Also called bubble down, percolate down or heapify-down.. You'll also see "bubble up/down" and "percolate up/down": same thing.

peek is the easy one: return array[0] without changing anything.

Try it

Every comparison and swap is shown in both the tree and the array:

Things to try:

1. Press push( 5 ). It's the example above: two swaps, then it stops below the 3.
2. Press push( 51 ). It compares once with its parent and stops. Pushes are often much cheaper than the worst case.
3. Press push( 1 ). It climbs all the way to the root: one swap per level.
4. Pop a few times. The values come out in sorted order (1, 3, 5…) even though the array is never sorted.
5. Switch to max-heap and pop: the biggest comes out first. Only the comparison changed.

Why "log n"?

Each step of a sift moves an item one level. A heap of n items has about log₂ nLogarithm (log₂ n)How many times you can halve n before reaching 1. log₂ 8 = 3, log₂ 1,000 ≈ 10, log₂ 1,000,000 ≈ 20. It grows very slowly: a thousand times more data adds only about 10. levels (§02). So:

• push does at most about log₂ n comparisons and swaps;
• pop does at most about 2 × log₂ n comparisons (it compares the two children with each other, then the smaller one with the item) and log₂ n swaps.

For a million items that's about 20 levels: roughly 20–40 comparisons, whatever the data. In Big-O notationBig-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles. notation, push and pop are O(log n): the cost grows with the number of levels, not with the number of items. peek is O(1): constant, however big the heap is.

Write one: a heap in Go and JavaScript

JavaScript has no built-in heap, so in JS you either write one or install a package. Go has container/heap (§05), but it's awkward enough that many teams write the small generic version below. Writing it once yourself is also the best way to make §03 stick.

The key design choice: the heap doesn't compare items with < directly. It asks a function you pass in, usually called less(a, b): "should a come out before b?". For a min-heap of numbers that's a < b. For a max-heap it's a > b. For ER patients it's a.urgency < b.urgency. One heap, any ordering.

package main

import (
	"cmp"
	"fmt"
)

// Heap keeps the "smallest" item (according to less) at index 0.
type Heap[T any] struct {
	items []T
	less  func(a, b T) bool // true if a should come out before b
}

func NewHeap[T any](less func(a, b T) bool) *Heap[T] {
	return &Heap[T]{less: less}
}

func (h *Heap[T]) Len() int { return len(h.items) }

// Peek returns the top item without removing it. O(1).
func (h *Heap[T]) Peek() (T, bool) {
	if len(h.items) == 0 {
		var zero T
		return zero, false
	}
	return h.items[0], true
}

// Push adds x at the end, then sifts it up. O(log n).
func (h *Heap[T]) Push(x T) {
	h.items = append(h.items, x)
	i := len(h.items) - 1
	for i > 0 {
		p := (i - 1) / 2 // parent
		if !h.less(h.items[i], h.items[p]) {
			break // parent is already smaller or equal: done
		}
		h.items[i], h.items[p] = h.items[p], h.items[i] // swap
		i = p
	}
}

// Pop removes and returns the top item. O(log n).
func (h *Heap[T]) Pop() (T, bool) {
	var zero T
	n := len(h.items)
	if n == 0 {
		return zero, false
	}
	top := h.items[0]
	h.items[0] = h.items[n-1] // move the last item to the root…
	h.items[n-1] = zero       // (clear the old slot so the GC can free it)
	h.items = h.items[:n-1]
	h.siftDown(0) // …and let it sink to its place
	return top, true
}

func (h *Heap[T]) siftDown(i int) {
	n := len(h.items)
	for {
		best := i
		l, r := 2*i+1, 2*i+2
		if l < n && h.less(h.items[l], h.items[best]) {
			best = l
		}
		if r < n && h.less(h.items[r], h.items[best]) {
			best = r
		}
		if best == i {
			return // smaller than both children (or a leaf): done
		}
		h.items[i], h.items[best] = h.items[best], h.items[i]
		i = best
	}
}

func main() {
	h := NewHeap(cmp.Less[int]) // min-heap of ints
	for _, x := range []int{5, 3, 8, 1, 9, 2} {
		h.Push(x)
	}
	top, _ := h.Peek()
	fmt.Println("peek:", top, "len:", h.Len())
	for h.Len() > 0 {
		x, _ := h.Pop()
		fmt.Print(x, " ")
	}
	fmt.Println()

	type Patient struct {
		Name    string
		Urgency int // 1 = most urgent
	}
	er := NewHeap(func(a, b Patient) bool { return a.Urgency < b.Urgency })
	er.Push(Patient{"sprained ankle", 4})
	er.Push(Patient{"heart attack", 1})
	er.Push(Patient{"broken arm", 3})
	next, _ := er.Pop()
	fmt.Println("treat next:", next.Name)
}

Output (Go 1.24; Node 22 prints the same, with size: 6 instead of len: 6):

peek: 1 len: 6
1 2 3 5 8 9
treat next: heart attack

Go's container/heap, demystified

Go's standard library ships a heap in container/heapcontainer/heapGo's standard-library heap package. You provide a slice type with five methods (Len, Less, Swap, Push, Pop); the package functions heap.Init, heap.Push, heap.Pop, heap.Fix and heap.Remove do the heap work.. It's older than generics (which arrived in Go 1.18), so instead of a Heap[T] type it works through an InterfaceInterfaceA list of method names (and their signatures) with no code. Any type that has those methods can be used wherever the interface is expected. In Go this happens automatically, without writing “implements”.: you describe your slice, the package does the algorithm.

The five methods

package main

import (
	"container/heap"
	"fmt"
)

type Patient struct {
	Name    string
	Urgency int // 1 = most urgent
}

// ER is a slice of patients that satisfies heap.Interface.
type ER []Patient

func (q ER) Len() int           { return len(q) }
func (q ER) Less(i, j int) bool { return q[i].Urgency < q[j].Urgency } // min-heap on Urgency
func (q ER) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }

// Push and Pop only touch the END of the slice. container/heap does the rest.
func (q *ER) Push(x any) { *q = append(*q, x.(Patient)) }
func (q *ER) Pop() any {
	old := *q
	n := len(old)
	p := old[n-1] // the item heap.Pop already moved to the end
	*q = old[:n-1]
	return p
}

func main() {
	q := &ER{{"sprained ankle", 4}, {"broken arm", 3}, {"fever", 5}}
	heap.Init(q) // arrange the existing items into a heap: O(n), see §06

	heap.Push(q, Patient{"heart attack", 1}) // NOT q.Push(…)
	for q.Len() > 0 {
		p := heap.Pop(q).(Patient) // NOT q.Pop()
		fmt.Printf("%d %s\n", p.Urgency, p.Name)
	}
}

1 heart attack
3 broken arm
4 sprained ankle
5 fever

Here's who does what:

The confusing part: two Pops

There are two functions called Pop, and they do very different things. heap.Pop(q) is the package function: it finds the winner and repairs the heap. Your q.Pop() method just removes the last element of the slice. Step through what happens inside one heap.Pop call:

1// container/heap (standard library)
2func Pop(h Interface) any {
3    n := h.Len() - 1
4    h.Swap(0, n)     // calls YOUR Swap
5    down(h, 0, n)    // calls YOUR Less and Swap
6    return h.Pop()   // calls YOUR Pop
7}
8 
9// your code
10func (q *ER) Pop() any {
11    old := *q
12    n := len(old)
13    p := old[n-1]    // take the LAST item
14    *q = old[:n-1]   // shrink the slice by one
15    return p
16}

So the rule is short: always call heap.Push(q, x) and heap.Pop(q). Your own Push and Pop methods exist only for the package to call. If you call q.Pop() yourself you get whatever happens to be at the end of the slice: in this example, sprained ankle instead of heart attack. Nothing crashes; the answers are just wrong.

The other package functions

• heap.Init(q) turns a slice in any order into a heap, in O(n) (§06).
• heap.Fix(q, i) re-sifts item i after you changed its priority; heap.Remove(q, i) removes the item at index i. Both are O(log n), and both need you to know where the item is (§07).
• Peek has no function: the top is simply (*q)[0], as long as q.Len() > 0. q is a pointer to the slice; *q follows the pointer to the slice itself, and the parentheses make Go do that first, then take index 0. (*q[0] would mean "index the pointer, then follow", which doesn't compile.)

Building a heap in O(n), and heapsort

Sometimes the data is all there at the start: a list of jobs loaded from a file, every number in an array. You could push them one at a time: n pushes × up to log₂ n levels each = O(n log n)Big-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles.. There's a faster way, called HeapifyHeapify (build-heap)Turning an unsorted array into a heap in place by sifting down every parent, from the last parent back to the root. Takes O(n), faster than pushing items one by one. (or "build-heap"), and it's what Go's heap.Init does.

The idea: fix small heaps, then join them

1. Put the items in the array in whatever order they came. The shape is already right; only the order is wrong.
2. Every leaf is already a valid heap on its own: a single item can't break the rule. In a complete tree, about half of all nodes are leaves (index n/2, rounded down, onward), so they need no work.
3. Go backwards through the remaining nodes, from the last parent (index n/2 − 1, with n/2 rounded down; 6 for 15 items) to the root. At each one, its two subtreesSubtreeA node together with everything below it. Every child of a node is the root of its own smaller tree — which is why tree code is usually recursive. (a child plus everything below it) are already valid heaps (you fixed them earlier). Only the node itself can be out of place, so sift it down (§03). Now its whole subtree is a heap.
4. When you reach index 0, the whole array is a heap.

Step through it on 15 numbers. Faded nodes are parents not handled yet:

Why it's linear: most nodes barely move

The cost of sifting a node down is at most its distance to the bottom. Look at where the nodes are in that 15-item tree:

The many nodes near the bottom can barely move; only the few near the top can move far. Pushing one by one is the opposite: the many late arrivals land at the bottom and may have to climb the whole height.

For any size, the sum works out the same way: n/4 nodes × 1 + n/8 × 2 + n/16 × 3 + … which adds up to less than n swaps in total: fewer than 1 swap per item on average. Each level of sinking costs 2 comparisons, so that's also about 2 comparisons per item, however big n gets. So heapify is O(n), and the table under the stepper shows it: about 2n comparisons for heapify, while pushing one by one grows much faster.

Heapsort, briefly

Heapify gives you a sorting algorithm almost for free. With a max-heap:

1. Heapify the array: O(n).
2. Swap the root (the biggest) with the last item. The biggest is now in its final place at the end.
3. Treat the array as one item shorter, and sift the new root down.
4. Repeat until one item is left. The array is now sorted from smallest to largest.

That's HeapsortHeapsortA sorting algorithm: heapify the array, then repeatedly swap the top to the end and shrink the heap by one. O(n log n) always, no extra memory, but not stable and usually slower in practice than the built-in sort.: O(n log n) in every case, and no extra memory because it works in placeIn placeWorking inside the input's own memory instead of building a copy, so only O(1) extra space is needed. slices.Reverse and JS's arr.reverse() are in place; arr.toReversed() returns a copy., inside the array itself. In practice it's slower than the built-in sorts, mostly because it jumps around the array (bad for the CPU cache), and it isn't StableStable (ordering)Equal items come out in the order they went in. Heaps are not stable on their own; add an increasing sequence number as a tie-breaker to make them so.: equal items can change order.

You'll rarely write it, but it's inside your language: Go's slices.Sort and sort.Sort use a quicksort variant (pdqsort): it splits the array around a chosen pivotPivotIn quicksort, the item the others are compared against to split them into “smaller” and “bigger”. A pivot near the middle splits the work in half; one at the edge barely splits it at all. value, smaller items to one side and bigger to the other. If its pivot choices keep turning out badly, it switches to heapsort, so the worst case stays O(n log n). (In the Go 1.24 and 1.26 source, look for heapSortOrdered in slices/zsortordered.go.)

Changing priorities: Fix, Remove, lazy deletion, tie-breaks

Real priority queues change while they wait. A patient's condition gets worse. A background job becomes urgent because the disk is nearly full. A timer is cancelled because the response arrived. All of these need to change or remove an item that is somewhere in the middle of the heap.

Finding an item by scanning the array would cost O(n) and defeat the point of the heap. There are two standard fixes.

Option 1: track the index, then heap.Fix

Give every item an index field and keep it correct inside Swap. To change a priority, edit the item, then call heap.Fix(q, item.index): it sifts the item up or down to its new place in O(log n). That's the Decrease-key / updateDecrease-key / updateChanging the priority of an item that is already in the heap, then moving it to its new correct place. Needs to know where the item sits in the array; Go's heap.Fix does the moving. operation.

package main

import (
	"container/heap"
	"fmt"
)

type Job struct {
	Name     string
	Priority int    // lower = more urgent
	seq      uint64 // arrival order: breaks ties, oldest first
	index    int    // where this job sits in the slice right now
}

type JobQueue struct {
	jobs    []*Job
	nextSeq uint64
}

func (q *JobQueue) Len() int { return len(q.jobs) }
func (q *JobQueue) Less(i, j int) bool {
	a, b := q.jobs[i], q.jobs[j]
	if a.Priority != b.Priority {
		return a.Priority < b.Priority
	}
	return a.seq < b.seq // same priority → first come, first served
}
func (q *JobQueue) Swap(i, j int) {
	q.jobs[i], q.jobs[j] = q.jobs[j], q.jobs[i]
	q.jobs[i].index = i // ← keep every job's index up to date
	q.jobs[j].index = j
}
func (q *JobQueue) Push(x any) {
	j := x.(*Job)
	j.index = len(q.jobs)
	j.seq = q.nextSeq
	q.nextSeq++
	q.jobs = append(q.jobs, j)
}
func (q *JobQueue) Pop() any {
	n := len(q.jobs)
	j := q.jobs[n-1]
	q.jobs[n-1] = nil // let the GC free it
	q.jobs = q.jobs[:n-1]
	j.index = -1 // no longer in the heap
	return j
}

// Update changes a job's priority and moves it to its new place: O(log n).
func (q *JobQueue) Update(j *Job, priority int) {
	if j.index < 0 {
		return // -1: already popped, no longer in the queue
	}
	j.Priority = priority
	heap.Fix(q, j.index)
}

func main() {
	q := &JobQueue{}
	backup := &Job{Name: "nightly backup", Priority: 5}
	for _, j := range []*Job{
		{Name: "send email", Priority: 2},
		backup,
		{Name: "resize image", Priority: 2},
		{Name: "charge card", Priority: 1},
	} {
		heap.Push(q, j)
	}

	q.Update(backup, 0) // disk almost full: the backup is urgent now

	for q.Len() > 0 {
		j := heap.Pop(q).(*Job)
		fmt.Printf("p%d %s\n", j.Priority, j.Name)
	}
}

p0 nightly backup
p1 charge card
p2 send email
p2 resize image

Three details make this work:

• The heap stores pointers ([]*Job). The caller keeps the same *Job (here backup) and can hand it to Update later; its index field always says where it is.
• Swap updates index on both jobs. Forget this and heap.Fix will repair the wrong slot, silently (§12).
• heap.Remove(q, j.index) deletes a job from the middle the same way: it swaps it to the end, repairs the heap, and calls your Pop.
• Pop sets index = -1, meaning "no longer queued". That's why Update checks for it: without the check, updating a job that was already popped would call heap.Fix(q, -1), and heap.Remove(q, -1) panics with index out of range [-1]. Check j.index >= 0 before either.

Option 2: lazy deletion

Sometimes you only need to cancel items, and cancelling happens a lot: most request timeouts are cancelled because the response arrived in time. Instead of finding the item, just mark it as cancelled, and throw it away when it reaches the top. That's Lazy deletionLazy deletion (stale entries)Instead of updating an item already inside a priority queue, push a new, better copy and skip the old one when it's eventually popped. Simpler code, slightly bigger queue.:

// Uses the MinHeap class from §04.
class TimerQueue {
  #heap = new MinHeap((a, b) => a.at < b.at);
  add(id, at) {
    const t = { id, at, cancelled: false };
    this.#heap.push(t);
    return t; // the handle: keep it if you might cancel later
  }
  cancel(t) { t.cancelled = true; } // O(1): no searching the heap
  popDue(now) {
    const due = [];
    while (this.#heap.size > 0 && this.#heap.peek().at <= now) {
      const t = this.#heap.pop();
      if (t.cancelled) continue; // cancelled: throw it away now
      due.push(t.id);
    }
    return due;
  }
}

const tq = new TimerQueue();
tq.add("retry", 100);
const ping = tq.add("ping", 150);
tq.add("timeout", 200);
tq.cancel(ping);
console.log(tq.popDue(250)); // [ 'retry', 'timeout' ]

Cancelling is now O(1), and no index tracking is needed. Notice that cancel takes the entry object that add returned (a "handle"), not the name "ping". Names get reused: a "retry" timer that already fired, or a request id that comes back later. If you cancelled by name and kept a list of cancelled names, an old cancel could silently swallow a brand-new timer with the same name. A flag on the entry itself only ever affects that one entry. (setTimeout works the same way: it returns a handle you pass to clearTimeout.)

The price is memory: cancelled items stay in the heap until they reach the top. If you cancel far more than you fire, the heap fills with dead entries. The usual guard is to rebuild the heap (heapify, §06) from only the live items once the dead ones pass some fraction of it. Go's own RuntimeRuntimeCode that ships inside every program of a language to support it while it runs. Go's runtime schedules goroutines and manages memory; Node's includes the event loop. does exactly this with its timers (§10).

Equal priorities: heaps are not first-come, first-served

A heap doesn't promise any order between equal items. Push five jobs with priority 2 (A, B, C, D, E), then one with priority 1 (X), into the MinHeap from §04, comparing only priority. They came out in this order (Node 22):

no tie-break:   X C E D A B
with seq:       X A B C D E

X is first, as it should be, but the five equal jobs got shuffled by the swaps. That's not a bug in the heap: heaps simply aren't stableStable (ordering)Equal items come out in the order they went in. Heaps are not stable on their own; add an increasing sequence number as a tie-breaker to make them so.. If the order matters (and in a job queue, it usually does: people expect fairness), add an increasing sequence number to every item and use it to break ties, exactly like seq in the Go code above:

let seq = 0;
const q = new MinHeap((a, b) => a.prio !== b.prio ? a.prio < b.prio : a.seq < b.seq);
for (const name of ["A", "B", "C", "D", "E"]) q.push({ name, prio: 2, seq: seq++ });

Why not use the arrival time instead? Date.now() only counts milliseconds, so two items often share one, and even nanosecond clocks can return the same value twice. A counter never repeats.

Top-K: the biggest few out of millions

"Show the 10 slowest requests from today's logs." "Top 100 products by sales." "The 5 users with the most failed logins." These are all Top-KTop-KFinding the K largest (or smallest) items out of many, e.g. the 10 slowest requests out of a billion. Classic trick: a min-heap of size K whose root is the item to beat. questions. The obvious answer is to sort everything and take the first K. It works, but it holds all the data in memory and does O(n log n)Big-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles. work to put a billion items in order when you only wanted 10 of them.

Why a min-heap for the biggest items?

It sounds backwards, so think of a club with K chairs. When someone new arrives, the only question is "are you better than the worst person currently sitting?" If yes, the worst person leaves and the newcomer sits down. If no, the newcomer goes home.

So you need instant access to the worst member of the top K, and for "biggest", the worst is the smallest. A min-heap puts exactly that item at the root.

A worked example

Stream: 5, 1, 9, 3, 7, 8, 2, 6, K = 3.

Answer: 9, 8, 7. Now try it on 20 numbers, with K = 3 or 5:

The code

// TopK returns the k largest numbers, biggest first. Uses Heap[T] from §04.
func TopK(stream []int, k int) []int {
	if k <= 0 {
		return nil
	}
	h := NewHeap(cmp.Less[int]) // MIN-heap: the root is the weakest of the current top k
	for _, x := range stream {
		if h.Len() < k {
			h.Push(x) // still filling up
		} else if smallest, _ := h.Peek(); x > smallest {
			h.Pop()   // kick out the weakest…
			h.Push(x) // …and let x in
		} // else: x can't be in the top k; skip it after one comparison
	}
	out := make([]int, 0, h.Len())
	for h.Len() > 0 {
		x, _ := h.Pop()
		out = append(out, x) // comes out smallest first
	}
	slices.Reverse(out)
	return out
}

// fmt.Println(TopK([]int{5, 1, 9, 3, 7, 8, 2, 6}, 3))  →  [9 8 7]

What it costs

Every item costs one comparison with the root. Items that get in also cost a pop and a push, each about log₂ K steps. So the total is O(n log K) time and O(K) memory. For K = 10, log₂ K is about 3, so it's almost one pass over the data. Sorting is O(n log n) time and needs every item in memory at once.

Measured on this machine (a shared 4-core VM, Go 1.24, numbers vary run to run): the top 10 of 1,000,000 random ints took about 0.6–1.7 ms with a 10-item heap, versus 75–150 ms to copy and sort the whole slice with slices.Sort. Roughly 100× faster, and the heap version could have read the numbers straight from a file without storing them.

Want the K smallest instead? Flip everything: a max-heap of size K, and a newcomer gets in if it's smaller than the root.

Merging K sorted lists, and the running median

Merging K sorted lists

You have K lists, each already sorted. Maybe they're log files from K servers, each in time order, or K sorted files written by a database. You want one sorted list.

The next item of the output must be the smallest of the K front items. So put one item from the front of each list into a min-heap. Pop the smallest, write it out, and push the next item from the same list. The heap never holds more than K items. That's a K-way mergeK-way mergeCombining several already-sorted lists into one sorted list by repeatedly taking the smallest front item among them. Each list is read once, front to back — sequential I/O.:

type cursor struct {
	val  int
	list int // which input list
	pos  int // index inside that list
}

// MergeK merges k sorted slices into one sorted slice. O(n log k). Uses Heap[T] from §04.
func MergeK(lists [][]int) []int {
	h := NewHeap(func(a, b cursor) bool { return a.val < b.val })
	for i, l := range lists {
		if len(l) > 0 {
			h.Push(cursor{l[0], i, 0}) // the front of every list
		}
	}
	var out []int
	for h.Len() > 0 {
		c, _ := h.Pop() // smallest front item among all lists
		out = append(out, c.val)
		if next := c.pos + 1; next < len(lists[c.list]) {
			h.Push(cursor{lists[c.list][next], c.list, next}) // refill from the same list
		}
	}
	return out
}

// MergeK([][]int{{1, 4, 9}, {2, 3, 10}, {5, 6}})  →  [1 2 3 4 5 6 9 10]

Each of the n items is pushed once and popped once, and the heap holds at most K items, so the total is O(n log K). With K = 2 you don't need a heap at all (just compare the two fronts). Heaps start to pay off around K = 4 to 8; with K = 100 files, picking the smallest by scanning all 100 fronts would cost about 100 comparisons per item, while a heap of 100 is only about 7 levels deep.

This loop runs inside a lot of software:

• LSM databases (RocksDB, Cassandra, …) merge sorted files in the background. That's compaction, and with many input files it's a heap-driven K-way merge.
• External sorting: to sort 100 GB with 1 GB of RAM, sort 100 chunks of 1 GB one at a time, write each to disk, then K-way merge the 100 sorted files.
• Merging results from K shards or K servers, each already sorted by time or score.

The running median

The median is the middle value: half the numbers are below it, half above. Hospitals, payment systems and dashboards often want "median waiting time so far", updated every time a new number arrives. Sorting after every number would be wasteful.

The trick uses two heaps that split the numbers into halves:

• low, a max-heap holding the smaller half. Its top is the biggest of the small numbers.
• high, a min-heap holding the bigger half. Its top is the smallest of the big numbers.

Keep them balanced, so low has the same number of items as high or one more. Then the median is always at the tops: the top of low if the count is odd, or the average of both tops if it's even. Step through it:

// Uses the MinHeap class from §04. Passing (a, b) => a > b turns it into a max-heap.
class RunningMedian {
  #low = new MinHeap((a, b) => a > b);  // MAX-heap: the smaller half
  #high = new MinHeap((a, b) => a < b); // MIN-heap: the bigger half

  add(x) {
    if (this.#low.size === 0 || x <= this.#low.peek()) this.#low.push(x);
    else this.#high.push(x);
    // Rebalance so low has the same size as high, or one more.
    if (this.#low.size > this.#high.size + 1) this.#high.push(this.#low.pop());
    else if (this.#high.size > this.#low.size) this.#low.push(this.#high.pop());
  }

  median() {
    if (this.#low.size === 0) return undefined;
    if (this.#low.size > this.#high.size) return this.#low.peek();
    return (this.#low.peek() + this.#high.peek()) / 2;
  }
}

const m = new RunningMedian();
const seen = [];
for (const x of [5, 15, 1, 3, 8, 7]) {
  m.add(x);
  seen.push(m.median());
}
console.log(seen.join(" ")); // 5 10 5 4 5 6

Each add is a push plus at most one pop and one push: O(log n). Reading the median is O(1).

Heaps in the wild: timers, schedulers, shortest paths

Timers: a min-heap of deadlines

A busy server can have tens of thousands of timers at once: request timeouts, retries, keep-alive pings, setTimeout calls, time.AfterFunc callbacks (Go's "run this function after d"). The runtime doesn't check every timer on every tick. It needs just two things:

1. When is the next one due? That's a peek: sleep exactly until then.
2. Fire everything that's due. That's "pop while the top's deadline ≤ now".

Adding a timer is a push. That's precisely what a min-heap ordered by deadline is good at.

Go: one timer heap per P

In Go, each P has its own timer heap. A PP (Go scheduler slot)“Processor”: one of GOMAXPROCS slots in Go's scheduler. An OS thread must hold a P to run goroutines. When a thread gets stuck in a syscall, the runtime gives its P to another thread. is one of the GOMAXPROCSGOMAXPROCSHow many OS threads may run Go code at the same instant. Defaults to the number of CPU cores. "slots" in Go's scheduler that a thread must hold to run goroutines. Splitting timers per P means goroutines on different CPU cores rarely fight over one shared heap. When the scheduler looks for work, it also checks its P's heap and runs any timers that are due.

Two details from the RuntimeRuntimeCode that ships inside every program of a language to support it while it runs. Go's runtime schedules goroutines and manages memory; Node's includes the event loop. source (runtime/time.go, Go 1.24 and 1.26):

• The heap is 4-ary, not binary: const timerHeapN = 4. Each node has four children, so the heap is half as deep. §11 explains why.
• Stopped timers are not dug out of the heap right away. They're marked and counted as "zombies" and skipped when they reach the top: §07's lazy deletion. When zombies make up more than a quarter of a P's heap, the runtime cleans them out in one go.

(Go 1.23 also changed how time.Timer channels work and made unreferenced timers collectable by the garbage collector. The heap underneath stayed.)

Node.js: a heap of lists, on top of libuv's heap

Node's timers are layered:

• At the bottom, libuvlibuvThe C library underneath Node.js that talks to the operating system: it runs the event loop, waits for network and file I/O, and keeps track of timers., the C library that runs Node's Event loopEvent loopThe loop inside every JS runtime that repeatedly picks the next piece of waiting work (a callback) and runs it to completion on the single main thread., keeps its own timers in a min-heap ordered by due time. When two timers are due at the same moment, it breaks the tie with a sequence number, just like §07. Each turn of the loop, it sleeps until the soonest timer is due (or I/O arrives), then runs the due ones.
• On top, Node's JavaScript layer groups your setTimeout calls into one list per duration: all 100 ms timers in one list, all 5000 ms timers in another. Timers in one list are added in time order, so each list is already sorted by due time. Node then keeps a priority queue of those lists, ordered by each list's next due time. You can see it in Node 22: node --expose-internals exposes require('internal/timers').timerListQueue, an instance of the internal PriorityQueue.

Node's internal PriorityQueue is a binary heap with two twists: it's 1-based (the root is at index 1, so children are at 2i and 2i+1), and it accepts a setPosition callback so each list always knows its index, which is §07's index-tracking trick for re-sifting a list when its next due time changes. To see where timers fit into each turn of the loop, see the event loop, step by step.

Job schedulers: priority, deadline, or both

A worker pool that serves "the most important job next" is a priority queue with workers taking from it (see worker pools: priority and fairness). Typical keys:

The seq tie-breaker is §07's sequence number: same priority, first come, first served. One honest note: not every scheduler is a heap. Linux's CPU scheduler, for example, keeps runnable tasks in a balanced binary search tree (a fully sorted tree that stays shallow; see Trees), because it also needs ordered walks and removals from the middle.

Shortest paths: Dijkstra's algorithm

How does a maps app find the fastest route? The classic answer is Dijkstra's algorithmDijkstra's algorithmFinds the cheapest path from one start node to every other node when edge weights are zero or positive. It always expands the closest unfinished node next, using a priority queue.. It keeps a priority queue of places to visit, keyed by "best distance found so far", and always expands the closest unfinished place next. Every time it finds a shorter road to a place, it lowers that place's key: a decrease-key (§07), or with lazy deletion, push a new entry and skip the stale one later.

With a binary heap, Dijkstra runs in O((V + E) log V) for V places and E roads, instead of O(V²) with a plain list. The full algorithm, with a step-through, lives in Graphs: Dijkstra. Other graph algorithms use the same heap-driven loop: A* search (Dijkstra plus a guess of the remaining distance, so it heads toward the goal first) and Prim's algorithm (connect all places with the cheapest total road length by always adding the cheapest next road).

Staff-level: cache misses, d-ary heaps, starvation, timer wheels

Memory: each level is a jump

The array layout from §02 has no pointers, which is good. But a sift doesn't walk the array in order: from index i it jumps to 2i+1, then to about 4i, then 8i. Near the top of the heap those indexes are close together. Deeper down, each jump lands far away in memory, usually on a different Cache lineCache lineThe chunk of memory (usually 64 bytes) that a CPU core copies into its own fast cache. When two cores write to the same cache line, it has to bounce between them, which is slow. (the 64-byte chunk the CPU loads at a time). Once the heap is bigger than the CPU cacheCPU cacheSmall, very fast memory on the CPU chip (L1, L2, L3) that keeps copies of recently used data. Reading from cache takes ~1–10 ns; reading from RAM takes ~100 ns., every level near the bottom can cost a trip to RAM, about 100 ns. It's the same effect described in CPU caches: pointer chasing, just milder.

d-ary heaps: fewer levels, wider nodes

A d-ary heapd-ary heapA heap where each node has d children instead of 2. Shallower (about log_d n levels: how many times you can divide n by d before reaching 1), so fewer hops per operation, but each sift-down step compares d siblings. Go's runtime uses d = 4 for its timers. gives each node d children instead of 2. The index math generalises: children of i are at d·i + 1 … d·i + d, and the parent of i is (i − 1) / d, rounded down.

The trade-off:

• Fewer levels. log₄ n is half of log₂ n: a million items is 10 levels instead of 20. Push (sift up) compares only with the parent, so it gets about twice as cheap.
• More comparisons per level on pop. Sift-down must find the smallest of 4 children: 3 comparisons plus 1 against the item, instead of 2. But the 4 siblings sit next to each other in the array, usually in the same cache line, so those extra comparisons are cheap while the saved levels are expensive jumps.

That's why Go's runtime timer heap is 4-ary (§10): timers are pushed constantly (every timeout, every time.Sleep) and most are cancelled before they fire, so cheap pushes matter most.

What we measured. On this machine (shared 4-core VM, Go 1.24), pushing 1,000,000 random ints into a heap and then popping them all cost about 87–91 ns per operation with a binary heap and 81–86 ns with a 4-ary heap: roughly 5% faster. An 8-ary heap was slower than both. At 1,000 items (which fit in the cache) all of them took about 30 ns. Runs taken while the VM was busy swung by 2×, which swamps a 5% difference. That's the honest lesson: d-ary heaps help most with big heaps, push-heavy use and larger items, but the win is modest. Measure with a BenchmarkBenchmarkA small program that runs one piece of code many times and measures how long it takes (and, in Go with -benchmem, how many bytes and allocations it makes per run). on your own data before you switch.

Starvation and priority inversion

A priority queue does exactly what you ask: the most urgent item always wins. Under sustained load, that becomes a problem.

• StarvationStarvationA task that is ready to run never gets its turn, because others keep getting the resource first. The system as a whole makes progress; that one task doesn't.. If urgent jobs keep arriving, a low-priority job waits forever. It isn't slow; it never runs. The usual fix is AgingAgingRaising a waiting item's priority the longer it waits, so low-priority work eventually runs instead of starving forever.: the longer an item waits, the more its effective priority improves. With a heap you can't cheaply re-score everything every second, so a common trick is to order by a virtual deadline, arrivalTime + allowance(priority): high priority gets a small allowance, low priority a big one. A low-priority job's deadline eventually becomes the earliest in the queue, so it must run. Other options: reserve a share of workers for low priority, or take one low-priority job after every N urgent ones (more in worker pools).
• Priority inversionPriority inversionA high-priority task ends up waiting for a low-priority one, e.g. because the low one holds a lock it needs, while medium-priority work keeps the low one from finishing. The priorities effectively flip.. A high-priority task waits for a lock held by a low-priority task, and medium-priority tasks keep the low one from running, so the high one waits behind the medium ones. Priorities have flipped. Operating systems fix this with priority inheritance: the lock holder temporarily borrows the waiter's priority. In application code the lesson is: priority only protects work that never waits on lower-priority work. A "high-priority" request that needs a connection from a pool busy with batch jobs isn't high priority any more.

Timer wheels: when there are millions of timeouts

A heap costs O(log n) per timer added. With millions of connections, each with idle, read and write timeouts that are reset on every packet, that adds up. Most of those timeouts are cancelled before they fire, and they rarely need exact precision.

A Timer wheelTimer wheelA ring of buckets, one per clock tick. A timer is dropped into the bucket for its tick (O(1)) and fired when the hand reaches it. Used for huge numbers of timeouts, e.g. in Linux and Kafka. drops the ordering entirely:

Adding and cancelling are O(1): compute the slot, add to or unlink from that slot's list. The price is precision: a timer fires on the tick, not at the exact nanosecond. Timers far in the future need coarser wheels on top (like the hour and minute hands of a clock); that's a hierarchical timing wheel. The Linux kernel's timer wheel and Kafka's request purgatory use them; so does Netty's HashedWheelTimer for network timeouts. Rule of thumb: heap for exact timers in the thousands; wheel for approximate timeouts in the millions.

When not to use a heap

• Small n. With a few dozen items, a sorted slice (binary search, then insert) or even a linear scan is simple and fast. On this machine, with 16 items, a sorted slice and a heap both took around 30–60 ns per pop+insert, which is far too small to matter. At 10,000 items, the sorted slice took about 1.3–2.2 µs versus 85–220 ns for the heap: 10× or more. Pick the simplest code until n says otherwise.
• You need more than the minimum. Iterating in order, finding an arbitrary key, range queries ("all jobs due between 10:00 and 10:05"), or "the second-best" cheaply: use a balanced search tree or a sorted structure (see Trees: choosing a sorted structure). A heap only knows its top.
• Everything has the same few priorities. With, say, 3 priority levels, use 3 plain FIFO queues and always serve the highest non-empty one. That's O(1) per operation and first-come, first-served for free.
• Many goroutines or threads share it. A heap is not safe for concurrent use: two pushes at once can corrupt the array. Protect it with a LockLock (mutex)A “do not disturb” sign for a piece of data: only the task holding the lock may touch it; others wait their turn., or give it one owner goroutine fed by a channel. If that lock becomes a bottleneck, shard it: one heap per worker or per P, like Go's timers, with Work stealingWork stealingEach worker has its own queue; a worker whose queue is empty takes (steals) work from a busy worker's queue instead of sitting idle. Go's scheduler does this with goroutines. when one runs dry. See locks for the basics.

Pitfalls gallery

q.Push(Patient{"heart attack", 1}) // just appended, never sifted up
p := q.Pop().(Patient)             // whatever is last in the slice

heap.Push(q, Patient{"heart attack", 1})
p := heap.Pop(q).(Patient) // the most urgent patient

job.Priority = 0 // the heap doesn't know

job.Priority = 0
heap.Fix(q, job.index) // move it to its new place

const h = new MinHeap((a, b) => a - b); // number, not boolean
// pushing 5 3 8 1 9 2 and popping gives: 2 9 3 8 1 5

const h = new MinHeap((a, b) => a < b); // boolean
// pushing 5 3 8 1 9 2 and popping gives: 1 2 3 5 8 9

Check yourself

Predict the answer before you click. Every question is covered above: Q1–Q2 in §02, Q3 in §05, Q4 in §08, Q5 in §06, Q6 in §07.

q := &ER{}             // heap.Interface from §05
heap.Push(q, Patient{"fever", 5})
heap.Push(q, Patient{"heart attack", 1})
heap.Push(q, Patient{"broken arm", 3})
p := q.Pop().(Patient) // ← note: q.Pop, not heap.Pop
fmt.Println(p.Name)

Cheat sheet