React 任务调度

React 任务池

不同的fiber任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。
为了存储这些任务，React中有两个任务池：

// Tasks are stored on a min heap
var taskQueue = []; // 存储立即要执行的任务
var timerQueue = [];  // 存储可以延迟执行的任务

源码中任务的初始结构：

var newTask = {id: taskIdCounter++, // 标记任务idcallback, // 回调函数priorityLevel,startTime,   // 任务开始时间，时间点expirationTime, // 过期时间，时间点sortIndex: -1, // 排序（取值来自过期时间，因此值越小，优先级越高）
};

React 中一旦来了新任务，就会先用currentTime记录当前时间（performance.now()）或Date.now()，如果任务中有delay参数，那么任务开始执行时间startTime = currentTime + delay。接下来通过startTime > currentTime 如果成立，证明任务是可以延期的，那么任务进入timerQueue，否则进入taskQueue。

React中任务调度

如果找到优先级最高的任务？
以taskQueue为例， 它是动态的任务池。Array.sort对它排序可行，但不是最优方案，每次sort，平均时间复杂度是nlog(n)。可以考虑小顶堆。
为什么不是大顶堆呢？因为taskQueue的newTask中的排序用的是sortIndex，这个值取自过期时间expirationTime，意味着优先级越高的任务越需要立马执行，那么过期时间自然就越小了（优先级越高，过期时间越小。） 当然也有可能两个任务的过期时间一样，那这时就要看谁先进的任务池了，也就是newTask中的id，每次来了新任务，id都会加1。
所以React源码中任务比价优先级的函数如下：

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

用到最小堆，就是把taskQueue做成最小堆的数据结构，然后在执行任务的时候，取最小堆的最小任务，如果任务处理完毕，那么需要把这个任务从taskQueue中删除，并重新调整剩下的任务池，依然保证它是最小堆的数据结构。当然，往taskQueue中插入新任务的时候，也要调整taskQueue，保证新的任务池仍是最小堆。

最小堆