01 / The idea
Keep a winner at the root.
You rarely write one of these, and you lean on them all day. Go and Rust ship one in the standard library, and the runtimes under your frontend keep their own. Each one answers the same question, over and over: what runs next?
With a handful of pending jobs, an array and a scan are easy: find the highest priority, take it, repeat. It gets expensive when new jobs keep arriving between those picks, because every pick scans everything again. A heap does less. After each change it repairs only a small part of its order.
02 / Name the rule
Keep the tree complete, and every parent ahead of its children.
A priority queue answers one question: which pending item goes first? A binary heap is the usual way to build one. It is a complete binary tree: fill each level left to right before starting the next, with at most two children per node.
Ours is a max-heap. Its invariant, the rule that holds after every operation, is that each parent ranks ahead of its children. Follow that down every branch and the root ranks ahead of everything. Siblings can sit in any order, which is exactly why this is cheaper than sorting.
Take the next priority.
Enqueue adds a pending job. Peek observes the next one. Take removes it.
A tree in an array.
Store the levels consecutively. Index arithmetic locates each parent and child.
Urgency, then arrival.
Priorities run from 0 to 9. Higher goes first; equal priorities keep arrival order.
The tie rule is this queue’s choice. A heap on its own makes no promise about equal priorities, so we stamp each job with an arrival number and compare that second.
Why do those indices describe a tree?Dense storage, without node pointers
Number the slots from zero. For a node at index i, the children are at 2i + 1 and 2i + 2, when those indices are occupied. A non-root node’s parent is at floor((i − 1) / 2). Select a cell in the explorer below to check those
relationships.
Because the tree fills level by level, there are never gaps in the middle, so the array needs no empty slots. The edges in the drawing are index arithmetic, not stored pointers.
03 / Follow one operation
One operation, two views of the same entries.
The array starts as [9, 2, 4]. That is a valid heap, since 9 outranks both its
children, and it is plainly not sorted. Before you add profile-photo at priority
7, guess which entry it swaps with and where it stops.
Enqueue drops the new entry in the last slot and compares upward. Take removes the root, moves the last entry into the gap, and compares downward against the better child. Those are sift-up and sift-down. Watch both, step through the recorded comparisons, then try your own jobs.
The root is always next.
- i 0 · root 9 visible-thumbnail
- i 1 2 archive-export
- i 2 4 background-preview
Priority 9 is at the root. The array reads 9, 2, 4: heap order does not sort siblings.
Worker slot: free
A valid heap is not a sorted list.
Priority 9 sits at the root. Its children, 2 and 4, stay unsorted.
Reduced motion: choose a scene to see its completed state.
Read this scene
Priority 9 sits at the root. Its children, 2 and 4, stay unsorted.
Priority 9 is at the root. The array reads 9, 2, 4: heap order does not sort siblings. Array order: 9 visible-thumbnail, 2 archive-export, 4 background-preview.
Watch restarts when you return. Step through keeps your selected step. Try it starts a fresh queue each time you open it.
Why does one branch of repair work?The invariant and the stopping condition
Before insertion, the existing heap already obeys the rule. Appending a leaf introduces only one possible violation: the new entry might outrank its parent. Swap those two when needed, then repeat at the parent’s old position. Each swap goes up one level; repair stops at the root or when the parent ranks first.
After removal, only the replacement at the root may be misplaced. Compare the children and choose the one that ranks first. If that child outranks the replacement, swap. The promoted child now outranks both its sibling and the replacement; the next possible violation lies farther down that one branch. Stop when there is no child, or when the replacement ranks ahead of its best child.
04 / Read the shape
Give the heap an image queue’s rules.
Start with the small mechanism, then open In the wild. Both queues take the same jobs, pick the same next job, and report an empty queue the same way. Go leans on its standard heap. TypeScript spells out the comparisons and swaps, which is what the explorer recorded.
The image queue adds rules of its own: an id is a short lowercase slug, priority runs from 0 to 9, and a rejected job leaves the queue untouched. Take a job and its id is free again. Reads hand back copies, so nobody can quietly change a waiting job’s priority from outside. Section 05 shows why that matters.
TypeScript exposes the sift-up mechanism for a newly appended number. Go adapts a slice to container/heap. Each keeps the greatest priority at the root. The complete file supplies their imports.
// The prefix is already a max-heap; repair its newly appended last number.
export function siftUp(values: number[]): void {
let child = values.length - 1;
while (child > 0) {
const parent = Math.floor((child - 1) / 2);
if (values[parent] >= values[child]) break;
[values[parent], values[child]] = [values[child], values[parent]];
child = parent;
}
}
// [9, 2, 4] + 7 → [9, 2, 4, 7] → [9, 7, 4, 2]// container/heap uses our Less rule; greater-than makes a max-heap.
type Priorities []int
func (p Priorities) Len() int { return len(p) }
func (p Priorities) Less(i, j int) bool { return p[i] > p[j] }
func (p Priorities) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p *Priorities) Push(value any) { *p = append(*p, value.(int)) }
func (p *Priorities) Pop() any {
last := len(*p) - 1
value := (*p)[last]
*p = (*p)[:last]
return value
}
func basicExample() {
priorities := &Priorities{9, 2, 4}
heap.Init(priorities)
heap.Push(priorities, 7)
fmt.Println(heap.Pop(priorities)) // 9
}Reading the TypeScriptThe comparator, private entries, and optional traces
The basic helper assumes finite numbers and an already-valid heap before the last item
was appended. The application class adds validation, an ID set, and a private arrival
number. #ahead compares higher priority first, then earlier arrival. Both sifts
use that same rule.
#swap exchanges two array entries. Math.floor((child - 1) / 2) moves the search upward; the child formulas move it downward. null means that
Peek or Take found no job.
new JobQueue(true) turns on the teaching snapshots the explorer replays. Each
frame copies the public job values, so leave it off in real use. Replaying frames never runs
the operation again.
Reading the GoLess decides priority; heap.Pop coordinates the repair
container/heap calls the methods on our slice adapter. Here Less(i, j) means “i should be taken ahead of j,” so a greater numeric priority
wins. Equal priorities compare the private arrival numbers.
There are two methods named Pop to distinguish. The caller uses heap.Pop(&q.items), which maintains heap order. The adapter’s Pop removes the last backing slot
when the package asks it to. Calling that hook directly would bypass the operation we need.
The zero-value queue works as it is. (Job, bool) tells a job apart from absence.
Removed slots are cleared, and inspection returns its own slice. There are no locks, so one
worker at a time.
What would I normally use in application code?Go and Rust already ship a heap
The standard one. The priorities, id rules, and tie-breaking in this lesson are ours; the heaps underneath are theirs.
In Go, container/heap gives you the heap operations over any type that implements its interface. Its documented priority-queue
example keeps each item’s index and fixes a changed priority with heap.Fix. That is the indexed heap from section 07, already written for you.
In Rust, BinaryHeap is a max-heap over any Ord, and iterating it does not give sorted order. Its
documentation calls changing an element’s ordering while it sits in the heap a logic
error, which is the section 05 bug in writing. Our wrapper hands out copies so that cannot
happen.
TypeScript has no built-in heap. A small one like ours, or a well-tested package, is the usual answer.
The shared test cases check what a caller can see after every operation: the result, and which jobs are still pending, across ties, empty reads, errors, and arrivals between takes. The order of siblings inside each heap is free to differ between languages.
05 / Try a decision
The number changed. Did its position?
A photo scrolls into view, and you want to bump its priority. It sounds like changing one number. But the heap only works while every parent outranks its children, and a number changing in place can break that without anything moving. Imagine a careless update method. Decide what Peek returns now.
06 / Follow the cost
A million jobs, a few dozen comparisons.
Here is every operation at a glance, with n pending jobs. The rest of this section is why the repair rows get to say log n.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Peek | O(1) | O(1) | Reads the root and copies one job. |
| Enqueue | O(log n) amortized | O(1) amortized | Sift-up makes at most one comparison per level. Growing the backing array is amortized, and the pending-id check is O(1) on average. |
| Take the next job | O(log n) | O(1) | Worst case for the repair: sift-down makes at most two comparisons per level. Freeing the id is O(1) on average. |
| Inspect pending jobs | O(n) | O(n) | Copies every job in storage order, which is not sorted. |
| Every pending job in priority order | O(n log n) | O(n) | Copy and sort, or take every job and empty the queue. The heap does not keep this order for you. |
| Change one job’s priority | O(log n) average | O(1) | The upload queue in the frontend example keeps an id-to-index map, so finding the job is O(1) on average and the repair is O(log n). Without the map, finding it is an O(n) scan. |
| Hold n pending jobs | — | O(n) | The heap’s backing array plus the set of pending ids. |
Go back to the explorer. profile-photo swapped once, then one comparison with the
root stopped it. Take moved the replacement down one level. A repair only ever walks one path,
up toward the root or down toward a leaf, one level per step.
A complete tree has very few levels, because each level holds twice as many entries as the
one above it. With n entries there are floor(log₂ n) + 1 levels. Seven jobs fit in
3 levels, so a repair makes at most 2 swaps. A thousand jobs fit in 10 levels, and a million fit
in 20.
Sift-up compares once per level on its way up. Sift-down compares at most twice per level: once to pick the better child, once against it. Taking the next job from a million makes at most 38 comparisons, and neither repair ever looks down the other branch. That is where O(log n) comes from.
Go documents the same O(log n) for heap.Push and heap.Pop. Rust
documents something better for BinaryHeap::push: averaged over every possible
arrival order, it expects O(1).
These are comparisons, not milliseconds. The explorer’s trace copies the whole array at every step, which is why tracing stays off in real use. Growing the array, validating ids, and copying results are extra. And for a handful of jobs, a plain scan may well be quicker.
07 / Give it a real job
The worker asks when it has a free slot.
In the photo app, a session owns the queue. The UI decides which jobs are urgent and enqueues them. Whenever a worker has room, it takes the next job and starts processing, and a new arrival can change what comes next while that work runs.
Taking a job only takes it off the pending list. The image still has to be processed and its success acknowledged, and a lower-priority job that is already running keeps running. When the queue is empty, the worker needs its own way to wait.
The queue forgets a job the moment it is taken, so a crash afterwards loses it. Retries, durable storage, cancellation, and progress reporting are the surrounding system’s job.
One more real-world snag: if urgent work never stops arriving, background work waits forever. Arrival-order ties make equal priorities predictable, and that is not fairness. Real schedulers reserve room for background work, or raise a job’s priority the longer it waits, and that second fix is a priority change exactly like section 05.
When priorities or membership can changeFinding an entry is work of its own
Peek always knows where the winner is. A plain heap has no idea where any other job lives. An indexed heap keeps a map from id to array index and updates it on every swap, so it can find a job before repairing or removing it.
The other common design pushes a revised copy and marks the old entry stale, skipping stale entries when they surface at the root. That needs version numbers and a plan for stale entries piling up. This lesson’s queue does neither yet, and any cancellation has to guarantee a canceled job is never picked.
Ids here are unique only while a job is pending; a system that tracks running jobs may need a wider rule. The arrival counter runs out after 9,007,199,254,740,991 enqueues, and enqueue fails there rather than silently breaking tie order. A fresh queue starts over.
Build UIs?You already hand out priorities, and one day you will need to own the queue.
Where it already is in your components
You have handed out priorities before. startTransition in React marks an
update as interruptible: keep the input responsive, let the results wait. Under it,
React’s scheduler stores its ready tasks in a min-heap keyed by expiration time, and the
root is what runs next. The browser offers the same decision as an API: scheduler.postTask takes user-blocking, user-visible, or background, and keeps a queue for each priority. Neither
is this lesson’s heap or its numeric policy. Both are the same decision, made for you.
When you have to own it
A photo grid with hundreds of uploads pending. The ones on screen should go first, and what is on screen changes as the user scrolls. A first-in, first-out queue uploads whatever was dropped first. Re-sorting the whole list on every scroll tick is n log n work to move a handful of items. A heap keeps the next pick at the root and repairs one branch when a priority changes.
Notice that reprioritizing has to find the item first. A plain heap does not know where an id lives, so the sample keeps the id-to-index map from the disclosure above, and it only touches the photos that came onto or left the screen. And removing a descriptor from the queue cannot reverse an upload that has already started; once processing begins, cancellation belongs to the worker.
Priorities you already assign: startTransition in React, postTask in the browser. React’s scheduler keeps its queue in a heap; the browser keeps a queue per priority.
import { startTransition, useState } from 'react';
import { search, type Photo } from './api';
export function Gallery() {
const [query, setQuery] = useState('');
const [results, setResults] = useState<Photo[]>([]);
function onChange(next: string) {
setQuery(next); // Urgent: the input must keep up with typing.
// Not urgent: React may interrupt this render for the next keystroke.
// Underneath, its scheduler keeps ready tasks in a min-heap ordered
// by expiration time. The root is what runs next.
startTransition(() => {
setResults(search(next));
});
}
return (
<>
<input value={query} onChange={(e) => onChange(e.target.value)} />
<ul>
{results.map((photo) => (
<li key={photo.id}>{photo.title}</li>
))}
</ul>
</>
);
}
08 / Make the call
How much order does the caller need?
A heap earns its place by keeping the next pick ready while items arrive and leave. If a screen needs every job displayed in order, that asks for more than the root can give you, so count it when you choose.
| The workload | A useful starting point | What to consider |
|---|---|---|
| A few pending jobs | Array plus a scan | Small code, simple inspection, and a full scan for each next selection. |
| Continued arrivals and repeated priority removal | Binary heap | Keep the next item at the root and repair along a branch after changes. |
| Display an entire ordered batch | Sort the batch | A heap’s backing array is not the sorted presentation you need. |
| Process strictly by arrival | FIFO queue | Priority comparisons add no useful rule to this requirement. |
| Only track the best item ever seen | One running best value | This does not retain the other candidates for later removal. |
09 / Take the idea with you
Keep enough order to make the next choice.
Explain the idea without its name: “Each parent ranks ahead of its children, so the root identifies the next job. After an insertion or removal, repair the one branch that may have become out of order.”
From memory, draw [9, 2, 4] as a tree. Explain why it is valid. Then add 7 and trace
its first comparison. Finally, decide what should happen when two jobs have priority 7. That last
answer comes from the application’s tie policy.
Then think of a pile of pending work in your own app. Does the caller need the next item, all of them in order, or one particular id? The answer tells you whether you want a heap, a sort, a lookup, or a heap with a lookup beside it.
Connections to follow nextRelated lessons
- Stack chooses by recency. A heap chooses through a comparison rule.
- Strategy gives replaceable decision rules a boundary. A queue’s comparison policy needs to remain consistent while entries are stored.
- Hash map finds an entry by key. Keep one beside a heap, mapping each id to its index, and you have the indexed heap from section 07.
- Queue and deque keeps arrival order, the rule this queue only uses to break ties.