小思考
刚刚遇到小明，问了他一个问题: 给你一个数字数组，找出最小的数字，怎么整？
小明：Array.sort！
我：如果这个数组是动态的，每次我都要找最小值，找到之后就从数组里删除这个元素，然后下次还想找最小值，怎么整。并且这个过程中，还会不断有新的数字插入数组。
小明：Array.sort！
我：可是数组是动态的，每次sort，但是我只要最小值，你浪费那么多时间把第二和第一万都排那么准确，不觉得在浪费时间吗？
小明：好像确实是浪费时间。可能是个算法吧，没做过。
React中的任务池
其实这不是个纯算法题，说回React，大家肯定听过React中有个fiber任务吧，而且不同的fiber任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。
为了存储这些任务，React中有两个任务池，源码中定义如下：
代码语言：javascript复制// Tasks are stored on a min heap
var taskQueue = [];
var timerQueue = [];taskQueue与timerQueue都是数组，前者存储的是立即要执行的任务，而后者存的则是可以延迟执行的任务。
源码中任务的初始结构定义如下：
代码语言：javascript复制 var newTask = {
id: taskIdCounter , // 标记任务id
callback, // 回调函数
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源码中任务比较优先级的函数如下：
代码语言：javascript复制function compare(a, b) {
// Compare sort index first, then task id.
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}其实用到最小堆，也就是把taskQueue做成最小堆的数据结构，然后执行任务的时候，取最小堆的最小任务，如果任务执行完毕，那么需要把这个任务从taskQueue中删除，并重新调整剩下的任务池，依然保证它是最小堆的数据结构。当然，往taskQueue中插入新任务的时候，也要调整taskQueue，保证新的任务池仍然是最小堆。
最小堆
了解最小堆之前，先来熟悉三个基本数据结构的概念：
二叉树
是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
从图形形态上看，满二叉树外观上是一个三角形。
如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
注意： 关于满二叉树定义这里，国内外定义有分歧，本文采用的是国内定义。满二叉树英文是Full Binary Tree，是指所有的节点的度只能是0或者2。
如下图，国外也认为是Full Binary Tree：
而对于我们本文所说的满二叉树，国外的概念叫完美二叉树。
完全二叉树
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。叶子结点只可能在最大的两层出现。
最小堆
是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。
如对于上面这个最小堆来说，经过观察，对应的深度与数组下标分别是：
经过观察，发现父子节点下标关系如下：
根据子节点下标推算父节点下标：parentIndex = (childIndex - 1) >>> 1
根据父节点下标推算子节点下标：
leftIndex = (index 1 )2 - 1,
rightIndex = leftIndex 1
至此，我们就可以尝试去实现最小堆的增(push)删(pop)查(peek)函数了：
peek
peek，瞄一下嘛，即获取最小堆的堆顶值。
代码语言：javascript复制export function peek(heap) {
return heap.length === 0 ? null : heap[0];
}push往最小堆中添加一个元素，因为taskQueue本身已经是最小堆，并且是数组存储，这时候为了尽可能多的复用原先的结构，我们可以先把新元素插入数组尾部，然后从下往上调整最小堆：
代码语言：javascript复制export function push(heap, node) {
const index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}怎么从下往上调整呢？因为最小堆的典型特点就是父节点比左右子节点都小，那这时候除了尾部元素，其他都是满足这个特点的。这个时候我们只需要调整尾部元素以及和尾部元素的祖先就可以了，一直往上调整，直到不再需要调整为止。代码如下：
代码语言：javascript复制// 向上调整最小堆
function siftUp(heap, node, i) {
let index = i;
while (index > 0) {
// 父节点下标
const parentIndex = (index - 1) >>> 1;
// 父节点
const parent = heap[parentIndex];
if (compare(parent, node) > 0) {
// parent>node, 不符合最小堆
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
// 已经符合最小堆，上面的祖先本身就是最小堆结构，因此停止调整
return;
}
}
}pop
删除堆顶元素。即React一个任务执行完了，那么肯定要把这个任务从任务池taskQueue中删除。问题来了，怎么删除呢，堆顶元素其实就是taskQueue[0]，这个位置我们肯定还是要用的，并且和push一样，为了尽可能复用原先的最小堆结构，我们可以采取一个办法：把最后一个元素覆盖堆顶元素，然后从堆顶往下调整最小堆。
代码语言：javascript复制export function pop(heap) {
if (heap.length === 0) {
return null;
}
const first = heap[0];
const last = heap.pop();
// 如果堆顶和堆尾元素不相等，证明现在的元素总数>1，需要往下调整
if (first !== last) {
heap[0] = last;
siftDown(heap, last, 0);
}
return first;
}关于往下调整，其实就是检查每个子堆的结构，确保最小值在父节点，不满足就交换父与左或者父与右，代码如下，我加了尽可能多的详细注释：
代码语言：javascript复制function siftDown(heap, node, i) {
let index = i;
const len = heap.length;
const halfLen = len >>> 1;
while (index < halfLen) {
let leftIndex = (index 1) * 2 - 1;
let left = heap[leftIndex];
let rightIndex = leftIndex 1;
let right = heap[rightIndex];
// todo 比较parent与left与right的大小
// 如果parent不是最小的，那就比较left和right谁最小，然后把最小的和parent交换位置
// 如果parent是最小的，那就停止
if (compare(left, node) < 0) {
// left < parent
// 为了保证根节点最小，比较left和right
if (rightIndex < len && compare(right, left) < 0) {
// right<left, right是最小的，交换parent和right
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
// right>left, left是最小的，交换parent和left
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (rightIndex < len && compare(right, node) < 0) {
// left > parent
// 检查right, right<parent
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
// parnent最小
return;
}
}
}总结
至此，相信大家都已经学会了React任务调度与最小堆。
最后，我最近在写mini react，本文代码就是其中的一部分，欢迎关注，github地址是：https://github.com/bubucuo/mini-react
