Explainer · 7 June 2026

How heaps and priority queues work

Your job queue has three thousand background tasks. A payment webhook must jump ahead of a thumbnail resize. A health check should run before a nightly report. A regular FIFO queue cannot express that — you need a priority queue: always dequeue the most urgent item, not the oldest. The workhorse implementation is a binary heap, a nearly complete binary tree stored in a flat array where each parent is smaller than its children (a min-heap) or larger (a max-heap). Heaps power Dijkstra shortest-path search, Linux process priorities, hospital triage simulators, and the "top K trending tokens" widget on a dashboard. They are one of the few data structures where understanding the array index math unlocks most of the behavior.

Priority queue operations

Abstractly, a priority queue supports:

Insert — add an element with a priority.
Peek / find-min — read the highest-priority element without removing it.
Extract-min — remove and return the highest-priority element.
Decrease-key (optional) — lower an existing element's priority when you learn a better path or deadline.

A sorted array gives O(1) peek but O(n) insert. A balanced binary search tree gives O(log n) for everything but needs pointer chasing and more memory overhead. A binary heap hits the sweet spot: O(log n) insert and extract-min, O(1) peek, excellent cache locality because children live at predictable indices in one contiguous buffer.

Binary heap invariant and array layout

In a min-heap, every node is ≤ both children. The minimum always sits at index 0. For a node at index i:

Parent: (i - 1) / 2 (integer division)
Left child: 2i + 1
Right child: 2i + 2

The tree is nearly complete: all levels are full except possibly the last, which fills left to right. That shape guarantees the array has no holes — no wasted slots, no linked-list nodes. A max-heap flips the comparison: parent ≥ children, root holds the maximum. Languages expose both: Java's PriorityQueue is a min-heap by default; C++ std::priority_queue is a max-heap unless you pass std::greater.

Sift-up, sift-down, and O(log n) mutations

Insert: append the new value at the end of the array (next leaf slot), then sift up — swap with the parent while the child is smaller than the parent. At most tree-height swaps → O(log n).

Extract-min: save the root, move the last leaf into index 0, shrink the array, then sift down — compare the node with both children, swap with the smaller child, repeat until the heap property holds. Again O(log n).

Decrease-key: locate the element (you need a side index map from id → heap position for O(log n) lookup), assign the new priority, sift up. Many libraries skip explicit decrease-key and use lazy deletion: push duplicate entries with better priorities and ignore stale pops — the trick Dijkstra's algorithm relies on when edge weights are non-negative.

Build-heap in O(n), not O(n log n)

Turning an arbitrary array into a valid heap by inserting elements one-by-one costs O(n log n). Floyd's build-heap is faster: start at the last non-leaf index (n/2) - 1 and sift down each node toward the leaves. Most nodes are near the bottom where sift-down is cheap; the amortized analysis sums to O(n). That is why std::make_heap and Python's heapq.heapify are linear — useful when you already have a batch of priorities and need a queue structure in one pass.

Where priority queues show up in production

Shortest paths — Dijkstra and A* maintain a min-heap keyed by tentative distance. Each edge relaxation may push a better path; stale entries are skipped on pop.
CPU and I/O scheduling — runnable threads sit in priority queues; Linux CFS uses a red-black tree keyed by virtual runtime, but real-time classes and many embedded kernels still use binary heaps for fixed-priority tasks. See CPU process scheduling for how nice values and run queues interact.
Event-driven simulation — discrete-event simulators pop the next timestamped event from a min-heap instead of scanning all pending events.
Merge K sorted streams — seed a heap with the first element of each stream; each pop emits the minimum and pushes the next element from that stream. Complexity O(N log K) for N total items across K streams — how external sort merge phases and log aggregators combine shard outputs.
Top-K / streaming quantiles — maintain a size-K max-heap of the smallest candidates seen so far to track the K largest values in one pass over a firehose (DEX volume leaders, error counts by endpoint).
Timer wheels vs heaps — kernel networking stacks and game engines sometimes prefer hierarchical timer wheels for millions of coarse timeouts; heaps win when priorities are dynamic or K is modest.

Variants: d-ary heaps, Fibonacci heaps, and pairing heaps

A d-ary heap gives each node up to d children. Shallower trees mean fewer sift-up steps on insert but more comparisons per sift-down step. A 4-ary heap often beats a binary heap on insert-heavy workloads with cheap comparisons — some JVM GC remembered-set scanners use d-ary heaps for that reason.

Fibonacci heaps advertise O(1) amortized decrease-key and insert, making Dijkstra theoretically O(E + V log V) instead of O(E log V). The bookkeeping (cascading cuts, lazy consolidation) is heavy; in practice binary heaps plus lazy decrease-key win on real hardware because constant factors and cache behavior dominate.

Pairing heaps and binomial heaps sit between — simpler than Fibonacci, still support merge in O(log n). Know they exist for competitive-programming trivia; ship a binary heap unless profiling proves otherwise.

Heaps vs other ordered structures

Compared to skip lists or balanced trees, heaps do not support efficient search for an arbitrary key — only the extremum at the root. If you need "find user 48291" and "delete middle element," use a hash map plus tree, not a heap alone. Compared to hash tables, heaps order by priority, not by key identity. The combination HashMap<Id, HeapIndex> + heap array is the standard pattern when decrease-key must be real, not lazy.

Implementation pitfalls

Inverted comparator — mixing min-heap logic with a max-heap comparator silently returns the wrong extremum. Write unit tests on a three-element heap before trusting production traffic.
Non-comparable priorities — floating-point priorities that are NaN break total ordering. Tie-break with a stable secondary key (insertion sequence, node id).
Storing large objects in the heap — keep lightweight (priority, id) pairs in the heap; store payloads in a side table keyed by id. Swapping huge structs on every sift is slow.
Assuming decrease-key exists — Java's PriorityQueue has no decrease-key; Rust's BinaryHeap likewise. Plan for lazy re-insertion or maintain your own index map.
Off-by-one in child indices — forgetting to bounds-check 2i+1 and 2i+2 against heap.size() before compare causes rare segfaults on the last level.

Practical checklist

Confirm you need only extremum access — not arbitrary search or ordered traversal.
Pick min vs max heap to match "highest priority = smallest number" in your domain.
Use lazy decrease-key for Dijkstra unless profiling shows duplicate entries blow memory.
Prefer heapify when bulk-loading; repeated push when streaming.
Pair heap with a hash map when you must update priorities by stable id.
Benchmark against a sorted vector if K stays tiny (K < 16) — simplicity may win.