Heaps and Priority Queues: The Data Structure Behind Schedulers

A FIFO queue returns the earliest arrival. Schedulers instead may need the earliest deadline, highest business priority, or a combination of urgency and fairness. A priority queue exposes that policy while hiding storage.

The binary heap is the usual implementation because it maintains only the order needed to identify the best item. It does not fully sort the queue. That restraint gives $O(1)$ access to the best entry and $O(log n)$ insertion and removal with a compact array. Those bounds, however, are only the beginning of a scheduler design. Equal priorities need deterministic treatment, queued jobs need cancellation and priority changes, and stale or adversarial workloads can turn a theoretically sound queue into an operational problem.

The thesis is that a heap is useful only when its invariant matches a precise priority contract. We will derive its mechanics, run a scheduling example, add stability and indexed updates, compare binary and d-ary shapes, and define tests and metrics.

Separate the Priority Queue Contract from the Heap #

A priority queue stores entries and supports at least three operations:

• push(entry) adds a candidate.
• peek() observes the best candidate without removing it.
• pop() removes and returns the best candidate.

“Best” comes from a comparator. In a min-priority queue, compare(a, b) < 0 means a should be returned before b. A max-priority queue reverses that relation. The names min and max describe comparator order, not necessarily a numeric field; an entry can be ordered by a tuple such as (deadline, class, sequence).

The comparator must be deterministic, antisymmetric in sign, and transitive: if a precedes b and b precedes c, then a precedes c. A comparator consulting a changing clock or mutable state can reverse two stationary entries, making any stored arrangement invalid.

A min-heap maintains a weaker invariant than a sorted array:

Every parent compares before or equal to each of its children.

This guarantees that the root is globally minimal. If some other node were smaller, the path from that node to the root would contain a parent-child violation. Siblings and separate subtrees need no relative order. Iterating the backing array therefore does not produce priority order; only repeated pop operations do.

The backing array is therefore not a sorted API. To inspect the next ten jobs, pop from a copy or use a selection routine; the first ten cells are not necessarily next in priority order.

Encode a Binary Heap in an Array #

A complete binary tree fills every level from left to right. It maps to an array without pointers. For a zero-based index i:

parent(i) = floor((i - 1) / 2)
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

Completeness keeps height at floor(log2(n)). It also gives good locality: entries occupy contiguous memory, and moving an item swaps array cells rather than rewiring nodes.

Insertion appends at the next available cell, preserving the complete shape but possibly violating order with the parent. siftUp repeatedly swaps the entry with its parent until the comparator says the parent may remain first. Removal saves the root, moves the final entry into index 0, shortens the array, and uses siftDown to swap that entry with its better child until both child relationships are valid.

push(item):
  append item
  while item precedes its parent: swap them

pop():
  save root; move last item to root
  while a child precedes it: swap with the best child
  return saved root

Each swap moves one level, so push and pop take $O(log n)$ comparisons; peek is $O(1)$. Repeated pushes build in $O(n log n)$, but bottom-up construction is $O(n)$: sift down internal nodes from the last parent to the root. Most nodes sit near leaves and move only a short distance, making the summed work linear.

For n entries, the last internal node is floor(n / 2) - 1; every later cell is already a leaf. Heapify visits internal nodes in reverse index order so both child subtrees are valid before their parent is repaired. This ordering matters: a forward pass can move a violation into a subtree that has already been examined.

Work a Scheduler Queue Step by Step #

Suppose a worker runs one job at a time. Smaller numeric priority is more urgent, and jobs with equal priority should run in submission order. Five jobs arrive:

The comparator orders first by priority, then by sequence. After pushing A, B, and C, a valid heap array is [B, A, C]: B rises over A, while C may remain under B. Pushing D appends it after C. It compares before parent A, so they swap, but it does not compare before root B because both have priority 1 and B has the earlier sequence. Pushing E needs no movement.

index: 0  1  2  3  4
job:   B  D  C  A  E
key:  1/1 1/3 2/2 3/0 4/4

Popping returns B. The implementation moves E to the root, then compares its children D and C. D is better, so E swaps with D; on the next level it swaps with A. A possible resulting array is [D, A, C, E]. Repeated pops return D, C, A, and E.

A may appear before higher-priority C in an intermediate array because neither is the other’s ancestor. Only the root is globally ordered; repair after each pop reveals the next root.

Stable sequence preserves arrival order within one priority, but a stream of priority-1 jobs can starve E. The heap cannot repair an unfair comparator. Aging, weighted classes, quotas, or virtual runtime must become keys that are updated consistently.

Make Equal Priorities Stable and Deterministic #

A plain heap is not stable. If compare(a, b) returns zero, swaps caused by unrelated insertions and removals can reverse a and b. That may be acceptable for a numeric simulation, but scheduler nondeterminism complicates incident reconstruction, user expectations, and tests.

Stability is implemented by extending the key, not by changing heap mechanics. Assign each insertion a monotonically increasing sequence and compare (priority, sequence). For a min-heap:

type ScheduledJob = Readonly<{
  id: string;
  priority: number;
  sequence: bigint;
  payload: unknown;
}>;

function compareJobs(left: ScheduledJob, right: ScheduledJob): number {
  if (left.priority !== right.priority) return left.priority - right.priority;
  return left.sequence < right.sequence ? -1 : left.sequence > right.sequence ? 1 : 0;
}

Do not subtract large sequence numbers into number; precision loss can create a false tie. Fixed-width counters need an overflow policy, and persisted jobs need a queue-unique token across restarts, such as a database value or (epoch, counter).

Stability adds a field, tie comparison, and possibly contention around sequence assignment. If arbitrary within-class order is acceptable, omit it explicitly; accidental stability can vanish after an implementation change.

Deadline scheduling uses a similar tuple. Order by readyAt, then by business class, then sequence. Read the clock when creating or updating the entry, not inside the comparator. For wall-clock deadlines, clock corrections can move real time around a stored timestamp, so elapsed-duration timers should use a monotonic clock where the runtime provides one. Persisted calendar deadlines still need wall time, with a policy for overdue work after restart.

Support Cancellation and Priority Changes with an Index #

Schedulers rarely only push and pop. A customer cancels a queued export, a retry is delayed, or aging promotes a waiting job. Finding an arbitrary job by scanning the heap costs $O(n)$. An indexed priority queue adds a map from stable job ID to current array index. Lookup becomes expected $O(1)$, and removal or update takes $O(log n)$ to repair the heap.

Every swap must update both map entries. The critical invariant is:

for every live array index i. A helper such as swap(left, right) should own the array exchange and both map writes so sift operations cannot forget them.

To remove index i, move in the last entry and delete the removed ID. If the replacement precedes its parent, sift up; otherwise sift down. Sifting only downward is a common arbitrary-removal bug.

Priority update follows the same logic. Replace the immutable entry with a new one, preserving its sequence if stable arrival order should survive reprioritization. Compare old and new keys to choose a direction, or inspect the parent after replacement. Mutating an entry’s priority in place without repair violates the heap while leaving the array superficially intact.

Lazy invalidation instead marks cancellation in a set or version map and discards stale roots. It avoids indexed swaps when cancellation is rare, but retains memory and inflates pop cost. Track live versus physical size and rebuild beyond a ratio limit.

Bulk heap construction must build the position map from the final heap layout, not the input order. The simplest approach updates positions inside the same swap helper used by siftDown; rebuilding the map after heapify is also correct. A debug assertion that checks both directions, positions[id] === index and items[index].id === id, catches stale entries after removal.

External handles need a lifetime rule. Reusing a canceled job ID can make an old cancellation request target a new job. Reject reuse while a handle may survive, or include a generation in the handle and map key. This is the same stale-reference problem as a reused array slot, even though the heap invariant itself remains valid.

Decide When a D-Ary Heap Fits Better #

A d-ary heap gives each parent d children. Its height is approximately log_d(n), so an entry moves through fewer levels. The cost is that siftDown must inspect up to d children to choose the best. For zero-based index i, the first child is d * i + 1, and the parent is floor((i - 1) / d).

A higher branching factor can help insertion-heavy workloads because sift-up checks one parent per level; pop-heavy workloads scan more children. The crossover depends on layout, comparator cost, hardware, and operation mix, so fewer levels do not automatically mean faster operations.

Other structures serve different contracts. A sorted array gives fast peek but expensive insertion. An unsorted array gives cheap insertion but linear pop. Bucket queues can approach constant time when priorities occupy a small known integer range. Balanced trees support ordered traversal and neighbor queries that a heap does not. The heap is compelling when the dominant operation repeatedly asks for one best mutable candidate.

Guard Scheduler Semantics and Failure Modes #

Queue correctness does not imply scheduler correctness. Starvation is the clearest example. Strict priority lets high classes delay low classes indefinitely. Aging can improve fairness by lowering a waiting job’s effective numeric priority, but continuously time-dependent comparison is invalid. Update keys periodically, place jobs into aging buckets, or use a policy designed around virtual service rather than consulting time during comparison.

Unbounded queues turn overload into memory growth and stale work. Bound queued count or bytes, define shedding by class, and discard expired work. Urgent throughput can otherwise hide an accumulating low-priority backlog.

Long-running jobs cannot be fixed by queue order alone. Once a non-preemptive worker pops a job, a newly arrived urgent job waits for it. Bound job slices, use cooperative checkpoints, reserve workers by class, or support preemption where the execution model permits it. The heap only decides at dispatch boundaries.

Timer queues add a readiness condition to priority order. peek identifies the earliest readyAt, but the consumer must wait until that time or until a newly inserted job becomes the earlier root. Use a monotonic clock for elapsed waits and recompute the delay after wakeup. Notification and root inspection must share synchronization; otherwise an insertion between inspection and sleep can leave an earlier job waiting unnecessarily.

Duplicate IDs break an indexed queue unless push explicitly rejects or replaces them. NaN priorities break numeric comparators because every comparison with NaN is false. Infinite values may be valid sentinels or accidental poison; decide at input validation. Exceptions thrown by a comparator can leave an operation half-mutated unless comparison happens before destructive changes or rollback is defined.

Concurrency belongs outside the heap. Producers and consumers need synchronized ownership of array and index mutations, and waiting plus notification must avoid lost wakeups. Heap mechanics provide no blocking semantics.

Test the Invariant and Operate the Queue #

Unit tests should exercise empty operations, one entry, ascending and descending insertions, equal priorities, root removal, arbitrary removal, updates in both directions, duplicate IDs, and sequence boundaries. After every mutation in test builds, assert that each parent compares no later than every child and that every position-map entry points back to the matching array item.

Property-based tests can generate random operation sequences and compare the queue against a slow reference model: keep entries in a map, sort its values by the same comparator before each expected pop, and check IDs and payloads. Small randomized cases find swap bookkeeping errors quickly. Generate many equal priorities to stress stability, and repeatedly update or cancel the root, last entry, and internal entries.

Test the comparator independently with generated triples: sign symmetry should hold for each pair, and transitivity should hold whenever two comparisons establish an order. Also heapify random arrays and compare their complete pop sequence with a stable sorted reference. These checks separate comparator defects from tree-repair defects.

For the worked scheduler, an expected trace is concrete: pushing A through E must pop B, D, C, A, E. Updating E to priority 0 should move it to the next pop while preserving whatever sequence policy the contract states. Canceling C must remove it from both the heap and ID map. Rebuild tests should prove that bottom-up construction yields the same pop sequence as repeated pushes.

Record depth by class, oldest-job age, enqueue-to-start latency, expiration, cancellation and rejection counts, lazy-deletion physical versus live size, and operation latency. Growing depth with flat heap-operation time indicates insufficient service capacity, not a slow siftDown.

Heap diagnostics can still catch structural trouble. Sample comparisons or levels traversed per operation, count rebuilds, and expose d-ary configuration. Do not attach unbounded job IDs as metric labels. For incident inspection, provide a bounded, access-controlled view sorted from a copied snapshot rather than exposing internal array order as schedule order.

Start with the comparator contract. The heap maintains enough order to reveal its minimum, sequence resolves ties, and an index makes arbitrary mutation efficient. D-ary variants tune comparisons against height; boundedness, fairness, and execution remain scheduler policy. Those boundaries make semantics and costs testable under the real workload.