Understanding Binary Trees, Complete Binary Trees, and Binary Heaps in React's Scheduler (MinHeap)

This article, part of a React fundamentals series, introduces binary trees, complete binary trees, and binary heaps, and explains why React's task scheduler uses a min‑heap to prioritize tasks.

A binary tree is a tree structure where each node has at most two children, commonly referred to as the left and right sub‑trees, and the order of these children matters.

A complete binary tree is a binary tree in which every level except possibly the last is fully filled, and the last level is filled from left to right without gaps. The article includes an illustration of several complete binary trees.

A binary heap is a special kind of heap that must be a complete (or nearly complete) binary tree. It satisfies the heap property: each parent node is ordered with respect to its children. When the parent is greater than or equal to its children, the structure is a max‑heap; when the parent is less than or equal to its children, it is a min‑heap. An image shows the visual representation of a min‑heap.

React chooses a min‑heap because the smallest value (the earliest expirationTime) is always at the root, allowing the scheduler to quickly extract the highest‑priority task. ExpirationTime represents how soon a task should run; a smaller value means higher priority.

The SchedulerMinHeap implementation provides five core functions: push (insert a node), pop (remove the root), siftUp (bubble a node up), siftDown (bubble a node down), and peek (read the root without removing it).

Insertion (push) : The new node is appended to the end of the array and then repeatedly swapped with its parent until the heap property is restored. The article shows the source code for push and siftUp and a test case that inserts a node with sortIndex: 1 into an existing queue.

The parent index is calculated with the unsigned right‑shift operator: parentIndex = (index - 1) >>> 1 . This operation effectively divides the index by two and discards any remainder, yielding the integer position of the parent node.

Examples of the >>> operator ( 5 >>> 1 , 4 >>> 1 , etc.) are provided to illustrate how it performs an integer division by two.

The article also shows how a binary heap maps to an array, where the parent of node i is at (i - 1) / 2 (integer division).

Deletion (pop) : To remove the root, the last element replaces the root and then siftDown moves it down the tree until the heap property is satisfied. The source code for pop and siftDown is displayed, along with a step‑by‑step example that removes the root value 2 and re‑orders the heap.

The variable halfLength (computed as length >>> 1 ) limits the loop to the first half of the array because nodes in the second half are leaves and never need to be sifted down.

The peek function simply returns the first element of the array or null if the heap is empty, as shown in its concise implementation.

Finally, the article notes that the SchedulerMinHeap file is a largely self‑contained implementation and that the next article will continue exploring React's scheduler.