How does React schedule tasks using a heap?

Recently, I have been doing the output related to solving LeetCode problems. Some friends may be confused. After learning the algorithm, where is the algorithm used in the front end? Today we’ll take a look at how React uses a heap to maintain task queues.

The business scenario

React has many tasks, such as user click, user input, and setState, and these tasks have different priorities. For example, user clicks and inputs must be high priority tasks and priority response, while load and animation events must be lower priority.

How does React manage low-priority tasks when new high-priority tasks jump the queue?

The source address

There is a directory called Packages/Scheduler in the React source code. This directory is associated with the React task scheduling module. The SRC directory scheduler. js implements the task scheduler-related logic schedulerminheap.js implements the heap

Small top heap task scheduling

React has a set of rules that define the priority of each task. Finally, React wraps each task into a task object named newTask 319, which has two attributes: ID and sortIndex. SortIndex identifies the priority of the current task. Id identifies the sequence of tasks.

React taskQueue is simulated as a small top heap. The top heap’s compare logic compares tasks in priority sortIndex (task priority) and ids (task creation order) if the sortIndex is the same.

Since the nature of the heap is to maintain a maximum value at the top of the heap, each top task (corresponding to the first element in the task array) is the task with the highest priority in the current task queue, so it only needs to obtain the top task each time to execute.

After the top task is taken out, it only needs to balance the small top heap from top to bottom after bouncing heap operation, then the top of the heap maintains the task with the highest priority in the current task queue.

In order to maintain the task queue through the heap, the time complexity of obtaining the highest priority task is O(1), and the time complexity of balancing adjustment after insert and eout operation is O(logn), which is very efficient on the whole.

end

React task scheduler