Queues

Scheduler's main job is to accept callback functions, order them by priority, and run them when the browser can afford to spend time on JavaScript.

For example:

scheduleCallback(UserBlockingPriority, () => {
  someComputation1();
});

scheduleCallback(ImmediatePriority, () => {
  someComputation2();
});

scheduleCallback(NormalPriority, () => {
  someComputation3();
});

The expected execution order is:

Immediate -> UserBlocking -> Normal

That ordering is the responsibility of Scheduler's queues. React can break rendering work into smaller tasks, give each task a priority, and let Scheduler decide which task should run next without blocking the browser for too long.

What a Task Represents

In Scheduler, a task is the unit of work stored in a queue. It contains the callback to execute, the priority assigned to that callback, and timing fields that help Scheduler decide when the task should run.

The task shape looks like this:

export type Task = {
  id: number;
  callback: Callback | null;
  priorityLevel: PriorityLevel;
  startTime: number;
  expirationTime: number;
  sortIndex: number;
};

The queue does not need to understand every field. It only needs two ordering fields:

• sortIndex: the primary value used for ordering.
• id: the tie-breaker when two tasks have the same sortIndex.

This is why the heap implementation works with a smaller Node type:

type Node = {
  id: number;
  sortIndex: number;
};

A Task has more fields than a Node, but it still satisfies the Node shape because it has both id and sortIndex.

The Two Scheduler Queues

Scheduler keeps two queues:

var taskQueue: Array<Task> = [];
var timerQueue: Array<Task> = [];

taskQueue stores tasks that are ready to run. In this queue, sortIndex is set to the task's expirationTime:

newTask.sortIndex = expirationTime;
push(taskQueue, newTask);

The lower the expirationTime, the sooner the task should run. This lets expired or nearly expired work move toward the front of the queue.

timerQueue stores delayed tasks that are not ready yet. In this queue, sortIndex is set to the task's startTime:

newTask.sortIndex = startTime;
push(timerQueue, newTask);

The lower the startTime, the sooner the delayed task becomes eligible to move into taskQueue.

So the same heap implementation supports both queues, but each queue uses a different meaning for sortIndex:

Why Scheduler Uses a Min-Heap

Scheduler frequently needs to answer one question: "What is the next task I should consider?"

A simple array could answer that by sorting the whole array after every insertion, but that would be wasteful. A min-heap is a better fit because it keeps the smallest item at the front while avoiding a full sort on every operation.

In Scheduler, "smallest" means "most urgent according to sortIndex." For taskQueue, that is the earliest expiration. For timerQueue, that is the earliest start time.

The important operations are:

• push: insert a task and restore heap order.
• peek: read the highest-priority task without removing it.
• pop: remove the highest-priority task and restore heap order.

Comparing Tasks

The comparison function defines the ordering:

function compare(a: Node, b: Node) {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

If a.sortIndex is smaller than b.sortIndex, a should be closer to the front of the queue.

If both tasks have the same sortIndex, Scheduler compares id. Since id is incremented every time a task is created, the older task wins the tie. This gives Scheduler stable ordering for tasks with the same deadline or start time.

Reading the Next Task with peek

peek returns the first item in the heap:

export function peek<T extends Node>(heap: Heap<T>): T | null {
  return heap.length === 0 ? null : heap[0];
}

Because a min-heap keeps the smallest item at index 0, peek(taskQueue) gives Scheduler the ready task with the earliest expiration:

currentTask = peek(taskQueue);

For timerQueue, peek(timerQueue) gives Scheduler the delayed task with the earliest start time:

const firstTimer = peek(timerQueue);

That is how Scheduler can quickly decide whether there is ready work to run or a delayed task that needs a timeout.

Adding a Task with push

push inserts a node at the end of the heap array, then moves it upward until the heap order is restored:

export function push<T extends Node>(heap: Heap<T>, node: T): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

The helper siftUp compares the new node with its parent. If the new node is smaller, they swap places. This continues until the new node is either at the root or already larger than its parent.

That is why adding a high-priority task can move it close to the front without sorting the whole array.

Removing a Task with pop

pop removes the root of the heap, which is the item with the smallest sortIndex:

export function pop<T extends Node>(heap: Heap<T>): T | null {
  if (heap.length === 0) {
    return null;
  }

  const first = heap[0];
  const last = heap.pop();

  if (last !== first) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }

  return first;
}

After removing the first item, pop moves the last item to the root and calls siftDown. siftDown moves that item downward until the smallest remaining item is back at the root.

Scheduler uses pop(taskQueue) when a task finishes or when it finds a cancelled task at the front of the queue.

Moving Delayed Tasks into taskQueue

Delayed tasks do not execute directly from timerQueue. When their startTime arrives, Scheduler moves them into taskQueue:

pop(timerQueue);
timer.sortIndex = timer.expirationTime;
push(taskQueue, timer);

This step changes the meaning of sortIndex. While the task is delayed, sortIndex is startTime. Once the task is ready, sortIndex becomes expirationTime, so it can compete with other ready tasks by deadline.

That transition is the reason Scheduler can use two queues with one heap implementation.

Summary

Queues are the structure that make Scheduler efficient:

1. taskQueue stores ready tasks ordered by expiration time.
2. timerQueue stores delayed tasks ordered by start time.
3. Both queues are min-heaps backed by arrays.
4. peek gives Scheduler the next relevant task in constant time.
5. push and pop maintain heap order without sorting the entire queue.
6. id breaks ties when two tasks have the same sortIndex.

Once this queue model is clear, the rest of Scheduler becomes easier to follow: scheduleCallback creates tasks, the queues keep them ordered, and workLoop repeatedly asks taskQueue what should run next.