React 优先级调度器 Scheduler 的小顶堆原理
在 React 18 的并发渲染（Concurrent Mode）架构中，能够做到“高优先级用户交互（如输入打字）即时插队，低优先级后台渲染（如长列表 Diff）让出时间切片”的幕后功臣，正是独立维护的包——scheduler。
当我们深入scheduler的源码目录，会发现其核心任务队列既不是普通的 JavaScript 原生数组，也不是 FIFO（先进先出）的线性链表，而是两颗**小顶堆（Min-Heap）**二叉树：taskQueue和timerQueue。
为什么 React 会选择小顶堆？它又是如何在单线程的 JavaScript 环境中实现微秒级的高效任务抢占与调度的？
为什么是小顶堆：时间复杂度与动态排序的权衡
在并发调度场景下，系统中的任务具有动态的到期时间（Expiration Time）。
调度器需要以极高的频率执行两类核心操作：
- 获取当前最紧急的任务（Peek）：必须是全局到期时间最早（值最小）的那个任务；
- 弹出已完成任务并插入新任务（Pop & Push）：随着用户不断点击，新任务随时插入队列。
如果使用普通数组：
- 每次插入时进行全局
sort()，排序时间复杂度为 $O(N \log N)$，在大并发更新时开销极大； - 如果保持数组有序，插入操作需要移动后续元素，复杂度为 $O(N)$。
而**小顶堆（Min Heap）**二叉树拥有极致的算法特性：
- 查询堆顶最小元素（Peek）：$O(1)$ 常数时间；
- 插入新节点（Push & Sift Up 上浮）：$O(\log N)$；
- 移除堆顶节点（Pop & Sift Down 下沉）：$O(\log N)$。
在 React 中，小顶堆直接用扁平的 JavaScript 一维数组进行高效存储，无需创建额外的指针对象，对 V8 引擎的垃圾回收极其友好。
graph TD Node0["[0] Task(exp: 100ms) - 堆顶最紧急"] --> Node1["[1] Task(exp: 150ms)"] Node0 --> Node2["[2] Task(exp: 200ms)"] Node1 --> Node3["[3] Task(exp: 300ms)"] Node1 --> Node4["[4] Task(exp: 180ms)"]Scheduler 小顶堆核心算法实现
以下是提炼自 React 源码中SchedulerMinHeap.js的完整算法骨架：
export interface HeapTask { id: number; sortIndex: number; // 比较的键值：通常是 expirationTime 或 startTime } export class MinHeap<T extends HeapTask> { private heap: T[] = []; push(node: T) { const index = this.heap.length; this.heap.push(node); this.siftUp(node, index); } peek(): T | null { return this.heap.length === 0 ? null : this.heap[0]; } pop(): T | null { if (this.heap.length === 0) return null; const first = this.heap[0]; const last = this.heap.pop()!; if (last !== first) { this.heap[0] = last; this.siftDown(last, 0); } return first; } private siftUp(node: T, i: number) { let index = i; while (index > 0) { const parentIndex = (index - 1) >>> 1; // 无符号右移计算父节点下标 const parent = this.heap[parentIndex]; if (this.compare(parent, node) > 0) { // 父节点比当前节点大，不满足小顶堆性质，交换并继续向上爬升 this.heap[parentIndex] = node; this.heap[index] = parent; index = parentIndex; } else { return; } } } private siftDown(node: T, i: number) { let index = i; const length = this.heap.length; const halfLength = length >>> 1; while (index < halfLength) { const leftIndex = (index << 1) + 1; const left = this.heap[leftIndex]; const rightIndex = leftIndex + 1; const right = this.heap[rightIndex]; // 寻找左、右子节点中较小的那一个 if (this.compare(left, node) < 0) { if (rightIndex < length && this.compare(right, left) < 0) { this.heap[index] = right; this.heap[rightIndex] = node; index = rightIndex; } else { this.heap[index] = left; this.heap[leftIndex] = node; index = leftIndex; } } else if (rightIndex < length && this.compare(right, node) < 0) { this.heap[index] = right; this.heap[rightIndex] = node; index = rightIndex; } else { return; } } } private compare(a: T, b: T): number { const diff = a.sortIndex - b.sortIndex; return diff !== 0 ? diff : a.id - b.id; // 到期时间相同时按创建 ID 先来后到 } }双堆协同：taskQueue 与 timerQueue 的流转
在真实的调度运行中，React 维护了两个小顶堆：
timerQueue（延时任务堆）：存放未到开始时间（startTime > currentTime）的延迟任务，按startTime排序；taskQueue（就绪任务堆）：存放已经可以立即执行的任务，按expirationTime（到期时间）排序。
调度器的核心主循环（workLoop）逻辑如下：
- 在每次循环前调用
advanceTimers(currentTime)：检查timerQueue堆顶的任务，如果某个任务的startTime已经到达当前时间，将其从timerQueue弹出并推入taskQueue； - 取出
taskQueue堆顶的最紧急任务进行执行； - 如果当前帧（默认 5ms）时间切片耗尽且当前任务尚未执行完毕，Scheduler 挂起执行，利用
MessageChannel宏任务向主线程重新注册一个调度回调，让出主线程给浏览器响应用户输入或渲染绘制。
正是依托小顶堆极致的 $O(\log N)$ 运算效率，React 才能在每秒成百上千次的复杂并发更新中，始终游刃有余地掌控全局节奏。
