小思考
刚刚遇到小明，问了他一个问题: 给你一个数字数组，找出最小的数字，怎么整？
小明：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++, // 标记任务idcallback, // 回调函数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();
}