小思考
刚刚遇到小明，问了他一个问题: 给你一个数字数组，找出最小的数字，怎么整？
小明：Array.sort！
我：如果这个数组是动态的，每次我都要找最小值，找到之后就从数组里删除这个元素，然后下次还想找最小值，怎么整。并且这个过程中，还会不断有新的数字插入数组。
小明：Array.sort！
我：可是数组是动态的，每次sort，但是我只要最小值，你浪费那么多时间把第二和第一万都排那么准确，不觉得在浪费时间吗？
小明：好像确实是浪费时间。可能是个算法吧，没做过。
React中的任务池
其实这不是个纯算法题，说回React，大家肯定听过React中有个任务吧，而且不同的任务有不同的优先级，为了用户体验，React需要先处理优先级高的任务。
为了存储这些任务，React中有两个任务池，源码中定义如下：
// Tasks are stored on a min heap
var 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
如果这道题你懂了，那么最小堆算法就很简单了
了解最小堆之前，你需要了解二叉树，满二叉树，和完全二叉树
最小堆算法（需要先了解下位运算）
是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。
如对于上面这个最小堆来说，经过观察，对应的深度与数组下标分别是：
经过观察，发现父子节点下标关系如下：
根据子节点下标推算父节点下标：parentIndex = (childIndex - 1) >> 1
根据父节点下标推算子节点下标：
**leftIndex = (index +1 )**2 - 1,
rightIndex = leftIndex + 1
至此，我们就可以尝试去实现最小堆的增(push)删(pop)查(peek)函数了：
// 最小堆算法
export function push(heap, node) {
heap.push(node);
const last = heap.length - 1;
siftUp(heap, node, last);
}
export function peak(heap) {
return heap.length === 0 ? null : heap[0];
}
export function pop(heap) {
if (heap.length === 0) {
return null;
}
const first = heap[0];
const last = heap.pop();
if (first !== last) {
heap[0] = last;
siftDown(heap, last, 0);
}
// return first;
}
function siftDown(heap, node, i) {
let index = i;
const len = heap.length;
const halfLen = len >> 1;
while (index < halfLen) {
const leftIndex = (index + 1) * 2 - 1;
const rightIndex = leftIndex + 1;
const left = heap[leftIndex];
const right = heap[rightIndex];
if (compare(left, node) < 0) {
// left小
if (rightIndex < len && compare(right, left) < 0) {
// right小
swap(heap, index, rightIndex);
index = rightIndex;
} else {
// left小
swap(heap, index, leftIndex);
index = leftIndex;
}
} else {
// node小
if (rightIndex < len && compare(right, node) < 0) {
// right小
swap(heap, index, rightIndex);
index = rightIndex;
} else {
break;
}
}
}
}
// 向上调整最小堆
function siftUp(heap, node, last) {
let index = last;
while (index > 0) {
const parentIndex = last >> 1;
const parent = heap[parentIndex];
if (compare(node, parent) < 0) {
// parent大
swap(heap, last, parentIndex);
index = parentIndex;
} else {
// node大 不作调整
break;
}
}
}
function compare(a, b) {
const diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}
// 交换元素
function swap(heap, left, right) {
[heap[left], heap[right]] = [heap[right], heap[left]];
}
React中的任务调度（背后的算法就是最小堆算法）
简版
import { peak, pop, push } from "./minHeap";
// 模拟任务池
let taskQueue = [];
let taskIdCounter = 1;
// 调用这个方法往任务池增加任务
export function scheduleCallback(callback) {
const currentTime = getCurrntTime();
// 暂时当作都不可等待
const timeout = -1;
const expirtationTime = currentTime - timeout;
const newTask = {
sortIndex: expirtationTime,
id: taskIdCounter++,
callback,
expirtationTime,
};
push(taskQueue, newTask);
// 请求调度
requestHostCallback();
}
// 创建一个宏任务
function requestHostCallback() {
port.postMessage(null);
}
const channel = new MessageChannel();
const port = channel.port1;
channel.port2.onmessage = function () {
// 依次执行任务池中的任务
workLoop();
};
function workLoop() {
let currentTask = peak(taskQueue);
while (currentTask) {
const callback = currentTask.callback;
// 防止重复执行
currentTask.callback = null;
callback && callback();
// 执行完从任务队列清楚 并重新调整最小堆
pop(taskQueue);
currentTask = peak(taskQueue);
}
}
function getCurrntTime() {
return performance.now();
}