任务调度算法有哪些(简介任务优先级调度算法)-众学网

小思考

刚刚遇到小明，问了他一个问题: 给你一个数字数组，找出最小的数字，怎么整？

小明：Array.sort！

我：如果这个数组是动态的，每次我都要找最小值，找到之后就从数组里删除这个元素，然后下次还想找最小值，怎么整。并且这个过程中，还会不断有新的数字插入数组。

小明：Array.sort！

我：可是数组是动态的，每次sort，但是我只要最小值，你浪费那么多时间把第二和第一万都排那么准确，不觉得在浪费时间吗？

小明：好像确实是浪费时间。可能是个算法吧，没做过。

React中的任务池

其实这不是个纯算法题，说回React，大家肯定听过React中有个fiber任务吧，而且不同的fiber任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。

为了存储这些任务，React中有两个任务池，源码中定义如下：

// Tasks are stored on a min heapvar taskQueue = [];var timerQueue = [];

taskQueue与timerQueue都是数组，前者存储的是立即要执行的任务，而后者存的则是可以延迟执行的任务。

源码中任务的初始结构定义如下：

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源码中任务比较优先级的函数如下：

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，瞄一下嘛，即获取最小堆的堆顶值。

export function peek(heap) { return heap.length === 0 ? null : heap[0];}push

往最小堆中添加一个元素，因为taskQueue本身已经是最小堆，并且是数组存储，这时候为了尽可能多的复用原先的结构，我们可以先把新元素插入数组尾部，然后从下往上调整最小堆：

export function push(heap, node) { const index = heap.length; heap.push(node); siftUp(heap, node, index);}

怎么从下往上调整呢？因为最小堆的典型特点就是父节点比左右子节点都小，那这时候除了尾部元素，其他都是满足这个特点的。这个时候我们只需要调整尾部元素以及和尾部元素的祖先就可以了，一直往上调整，直到不再需要调整为止。代码如下：

// 向上调整最小堆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一样，为了尽可能复用原先的最小堆结构，我们可以采取一个办法：把最后一个元素覆盖堆顶元素，然后从堆顶往下调整最小堆。

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;}

关于往下调整，其实就是检查每个子堆的结构，确保最小值在父节点，不满足就交换父与左或者父与右，代码如下，我加了尽可能多的详细注释：

至此，相信大家都已经学会了React任务调度与最小堆。