为什么 React 调度器用小顶堆做任务队列：数据结构、排序与时间复杂度的取舍

React 的 Scheduler 本质是一个「任务队列 + 时间切片器」：任意时刻都可能有人提交任务，调度器要不断回答同一个问题——下一个执行谁？ 它的答案是按「过期时间」排序，谁先过期谁最紧急，先执行谁。

实现这个队列用的数据结构，不是数组加排序，也不是链表，而是一个几十行的小顶堆（Min-Heap）。这篇文章从队列的需求出发，对比各种方案的时间复杂度，讲清楚为什么堆是最优解。

需求：一个「永远能取到最紧急任务」的队列

调度器的核心逻辑对应三个高频操作：

1. push —— 新任务进来，插入队列
2. peek —— 看一眼下一个最紧急的任务（不删）
3. pop —— 最紧急的任务执行完，把它移出队列

「最紧急」= 过期时间最小。问题来了：用什么数据结构，才能让这三个操作都足够快？

朴素方案为什么不行

方案一：无序数组，取的时候全扫。 插入 O(1) 很爽，但每次取最紧急任务都要 O(n) 扫一遍，任务一多就跪。

方案二：每次插入后整体排序。 插入 O(n log n)。但调度器每进来一个任务就重排一次，而绝大多数插入根本不影响「下一个是谁」——为完整排序付出了用不到的代价。

方案三：有序数组 / 有序链表。 有序后 peek O(1)、pop O(1)，但插入要 O(n)：数组要整体移位，链表要遍历找位置。而调度器恰恰是「插入比删除更频繁」的场景（每帧可能提交很多任务，但每次只执行一个）。

关键洞察在于：调度器不需要队列完全有序，只需要随时知道「最小值是谁」、能高效插入、能高效取出最小值。这是一个标准的**优先队列（Priority Queue）**需求，而优先队列的教科书答案，就是堆。

小顶堆：只维护「部分有序」

堆是一棵完全二叉树。小顶堆满足一个性质：

任意节点的值 ≤ 它的两个子节点。

于是根节点永远是全局最小值——「最紧急的任务」就放在 heap[0]，peek 只需要 O(1) 读第一个元素。

因为它是一棵完全二叉树，所以可以不用指针、直接用数组存——React 源码里 type Heap<T> = Array<T> 就是这么干的。父子关系有闭式公式：

• 左子：2i + 1
• 右子：2i + 2
• 父节点：(i - 1) >>> 1

核心操作与时间复杂度

push：插入 → 向上冒泡（siftUp）

新节点先追加到数组末尾（可能在很深的位置），然后一路和父节点比较：比自己小就交换，直到重新满足堆性质。

// push 的 JS 实现：追加到末尾，然后一路向上冒泡（siftUp）
const heap = [5, 10, 15, 20, 25, 30, 40];

function push(node) {
  let i = heap.length;
  heap.push(node);
  while (i > 0) {
    const parentIndex = (i - 1) >>> 1; // 父节点下标
    if (heap[parentIndex] <= heap[i]) break; // 父更小 → 堆性质已满足，停止
    [heap[parentIndex], heap[i]] = [heap[i], heap[parentIndex]]; // 父 > 子 → 向上交换
    i = parentIndex;
  }
}

push(3);
console.log(heap); // [3, 5, 15, 10, 25, 30, 40, 20]

用三层堆走一遍。 假设这棵 3 层小顶堆里有 7 个任务，节点值就是 sortIndex（越小越紧急）：

        5
      /   \
    10    15
   /  \   / \
  20  25 30  40

数组：[5, 10, 15, 20, 25, 30, 40]

现在来了一个极紧急的任务 push(3)，它要被一路向上交换：

步骤	比较与操作	数组
1	追加到数组末尾	[5, 10, 15, 20, 25, 30, 40, 3]
2	3 < 父 heap[3]=20 → 交换	[5, 10, 15, 3, 25, 30, 40, 20]
3	3 < 父 heap[1]=10 → 交换	[5, 3, 15, 10, 25, 30, 40, 20]
4	3 < 父 heap[0]=5 → 交换	[3, 5, 15, 10, 25, 30, 40, 20]

看数组里那个 3 的位置：末尾 → 下标3 → 下标1 → 下标0。三次交换后它冒到了根，成为新的最紧急任务：

        3
      /   \
    5     15
   / \   / \
  10 25 30  40
  /
 20

从叶子冒泡到根恰好走了 3 步，正好是树高 log₂8 = 3，这就是新节点能走的最长路径了。所以 push = O(log n)。

为什么只和父节点比较，不用和兄弟节点比较？

因为小顶堆的性质只规定「父节点 ≤ 子节点」，完全不约束兄弟节点之间的顺序。左子树的 10 和右子树的 15 谁大谁小，堆根本不关心——它只保证全局最小值浮在根上。

拿一个「新节点恰好落在右叶子」的例子验证。在 [5, 10, 15, 20, 25, 30, 40, 22]（8 个节点）里插入 12，它落在下标 8，是节点 20 的右叶子，左兄弟是 22：

        5
      /   \
    10    15
   /  \   / \
  20  25 30  40
  / \
 22  12   ← 新节点（右叶子）

siftUp 依然只走祖先链：12 vs 父 heap[3]=20 → 交换；12 vs 父 heap[1]=10 → 10 < 12，停。全程没有碰过左兄弟 22：

        5
      /   \
    10    15
   /  \   / \
  12  25 30  40
  / \
 22  20

检查堆性质：12 ≤ 22 ✓、12 ≤ 20 ✓、10 ≤ 12 ✓——新节点和左兄弟谁大谁小，根本不影响正确性。而且父节点公式 (i-1)>>>1 对左右孩子都成立（2k+1 和 2k+2 的父节点都是 k），所以算法甚至不需要知道自己落在左叶子还是右叶子。

pop：取根 → 末尾补位 → 向下沉（siftDown）

// pop 的 JS 实现：取出根，末尾补到根，再一路向下沉（siftDown）
const heap = [5, 10, 15, 20, 25, 30, 40];

function pop() {
  const top = heap[0];
  const last = heap.pop();
  if (heap.length > 0) {
    heap[0] = last; // 末尾元素补到根
    let i = 0;
    while (i < heap.length >>> 1) {
      const left = i * 2 + 1;
      const right = left + 1;
      // 选左右子节点中更小的那个
      const minChild =
        right < heap.length && heap[right] < heap[left] ? right : left;
      if (heap[minChild] >= heap[i]) break; // 子节点都不更小 → 堆性质已满足，停止
      [heap[i], heap[minChild]] = [heap[minChild], heap[i]]; // 向下交换
      i = minChild;
    }
  }
  return top;
}

console.log(pop()); // 5
console.log(heap);  // [10, 20, 15, 40, 25, 30]

还是那棵三层堆，pop 根节点 5（根就是最紧急的任务，取走它）：

步骤	操作	数组
1	取出根 5，末尾 40 补到根	[40, 10, 15, 20, 25, 30]
2	40 与较小子节点 10 交换	[10, 40, 15, 20, 25, 30]
3	40 与较小子节点 20 交换	[10, 20, 15, 40, 25, 30]

看数组里那个 40 的位置：根 → 下标1 → 下标3。它一路下沉到「比自己小的子节点都不再存在」的位置，堆重新满足性质：

        10
      /   \
    20    15
   / \   /
  40 25  30

新堆顶是 10，是剩余任务里最紧急的。pop 从根下沉到叶子，步数 ≈ 树高，所以 pop = O(log n)。 注意 40 只下沉两层就停了——堆不需要把所有元素排好，只需要最小的那个浮在根上，这就是「部分有序」省下来的时间。

peek：直接读根

return heap.length === 0 ? null : heap[0];

peek = O(1)——这就是堆相对「每次排序」最大的价值：取最紧急任务是常数时间。

复杂度对比总表

实现	插入 push	取最小 peek	删除最小 pop	额外开销
无序数组	O(1)	O(n)	O(n)	—
每次全排序	O(n log n)	O(1)	O(1)	排序成本纯浪费
有序数组	O(n) 移位	O(1)	O(1)	插入时整体移动
有序链表	O(n) 找位	O(1)	O(1)	指针 + 遍历
二叉堆（React）	O(log n)	O(1)	O(log n)	无指针，数组紧凑

调度器的实际负载是「插入频繁、每次取一个」。堆把 push 和 pop 都压到 O(log n)、peek 压到 O(1)，是三个操作之间的最优均衡。

顺带两个和排序有关的事实：建堆（heapify）是 O(n) 而不是 O(n log n)，因为只有前一半节点需要 siftDown；而如果把堆里元素一个个 pop 出来，就是 O(n log n) 的完整排序——这正是堆排序（Heap Sort）。堆只是「排序排一半、够用就停」，所以它比全排序便宜得多。

React 调度器里怎么用

双键排序：sortIndex + id

React 的堆节点有两个排序键（对齐 React 19.x 的 SchedulerMinHeap.js）：

type Node = {
  id: number;
  sortIndex: number;
};

function compare(a: Node, b: Node): number {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

• 主键 sortIndex：任务的紧急程度（taskQueue 里 = 过期时间）
• 副键 id：递增的入队序号，保证相同紧急度的任务按入队顺序执行（FIFO）

这解决了纯按时间排序的不稳定性：同一优先级下，先来的先执行。

优先级 → 过期时间 → 堆

scheduleCallback 把优先级映射成「过期时间」，过期时间越小越紧急：

优先级	timeout	说明
ImmediatePriority	-1	立即过期
UserBlockingPriority	250ms	用户交互（点击/输入）
NormalPriority	5000ms	默认
LowPriority	10000ms	低优先级
IdlePriority	maxSigned31BitInt	基本永不过期

过期时间 = startTime + timeout，作为 sortIndex 塞进最小堆——堆顶永远是最紧急（最先过期）的任务。

双队列：taskQueue + timerQueue

const taskQueue: Array<CallbackNode> = [];   // 立即可执行的即时任务
const timerQueue: Array<CallbackNode> = [];  // 延时任务（startTime 未到）

• 无 delay 的任务 → taskQueue，sortIndex = expirationTime
• 有 delay 的任务 → timerQueue，sortIndex = startTime
• advanceTimers() 把到期的延时任务从 timerQueue 转入 taskQueue，并把 sortIndex 从 startTime 改成 expirationTime

workLoop：时间切片与堆协作

currentTask = peek(taskQueue);
while (currentTask !== null) {
  if (currentTask.expirationTime > currentTime && shouldYieldToHost()) {
    break; // 未过期但已到帧预算 → 让出主线程
  }
  const callback = currentTask.callback;
  if (typeof callback === "function") {
    currentTask.callback = null;
    const didUserCallbackTimeout = currentTask.expirationTime <= currentTime;
    const continuationCallback = callback(didUserCallbackTimeout);
    // 返回 continuation → 下次继续；否则 pop 掉
  } else {
    pop(taskQueue); // callback 为 null 的已取消任务
  }
  currentTask = peek(taskQueue);
}

• peek 拿到最紧急任务
• 执行完（无 continuation）就 pop，堆自动重整，下一个 peek 依旧是 O(1)
• 每执行一段就检查 shouldYieldToHost()（默认 5ms 帧预算），超了就 break，把主线程还给浏览器——这就是时间切片

cancelCallback：O(1) 的「惰性删除」

为什么不能直接从堆里删除？

堆只维护「父 ≤ 子」的局部有序，数组里存的是这份偏序关系，并没有记录「每个元素当前在哪个下标」。所以想删掉任意一个指定任务，只能先在数组里线性扫描找到它的下标——O(n)——再把它移走、重新维护堆性质——O(log n)，整体 O(n)。

对调度器来说这不可接受：任务可能随时被取消，取消本应是个轻量操作，不能是 O(n) 的。

React 的取巧：取消 = 打标记，删除推迟到「浮到堆顶」

function unstable_cancelCallback(task: CallbackNode) {
  task.callback = null; // 置空回调 = 打上「已取消」标记
}

任务不从堆里拿走，只是把它的 callback 置空，变成一个墓碑（tombstone）。真正的删除发生在它浮到堆顶的那一刻：workLoop 每次 peek 到堆顶任务时，看到 callback === null 就走 else 分支把它 pop 掉，然后继续看下一个：

currentTask = peek(taskQueue);
while (currentTask !== null) {
  // ...执行逻辑...
  const callback = currentTask.callback;
  if (typeof callback === "function") {
    currentTask.callback = null;
    const continuationCallback = callback(didUserCallbackTimeout);
    // 返回 continuation → 下次继续；否则 pop 掉
  } else {
    pop(taskQueue); // callback 为 null → 墓碑，直接移除
  }
  currentTask = peek(taskQueue);
}

注意这个 else 分支很重要：就算堆顶恰好是已取消的任务，也会立刻被 pop 掉、继续下一个——调度器绝不会被一个取消任务卡住。

延时任务的清理在 advanceTimers 里，同样是先看标记：已取消的延时任务直接从 timerQueue 丢弃，不转入 taskQueue：

function advanceTimers(currentTime: number) {
  let timer = peek(timerQueue);
  while (timer !== null) {
    if (timer.callback === null) {
      pop(timerQueue); // 已取消的延时任务，直接丢弃
    } else if (timer.startTime <= currentTime) {
      pop(timerQueue);
      timer.sortIndex = timer.expirationTime;
      push(taskQueue, timer); // 到期，转入即时任务队列
    } else {
      return;
    }
    timer = peek(timerQueue);
  }
}

代价与收益

方案	取消操作	清理时机	复杂度
真实删除	先 O(n) 找下标，再 O(log n) 重整	立即	O(n)
惰性删除（React）	置空 callback 字段	浮到堆顶时顺带 pop	O(1)

代价是：被取消的任务作为墓碑留在堆里，直到它浮到堆顶才真正消失。极端情况下（任务被大量取消但都没到堆顶），堆里会积攒一些空壳任务，占一点内存、每次堆顶弹出多 O(log n) 的清理。

为什么这笔买卖划算：

1. 取消是高频操作，删除不是——取消必须快，一个字段赋值 O(1)
2. 堆顶弹出本来就免不了——workLoop 反正要 peek，顺手把墓碑 pop 掉，清理成本摊进了既有操作，没有额外开销
3. 调度器的堆很小——同一时刻的待执行任务通常是个位数，积攒的墓碑有限
4. 堆顶是取消任务也不卡调度——else 分支直接 pop，继续下一个

顺带一提，另一个思路是给每个任务记录「它在数组里的下标」，删的时候直接定位——但这样每次 push / pop / 交换都要同步更新两个节点的下标，给热路径加负担。React 选择了更省事的墓碑方案：用「任务多留一会儿」换「取消永远很便宜」。

总结

回到开头：调度器要「频繁插入、每次取最紧急的一个」。各方案对比：

• 无序数组：插入快，但取最紧急 O(n)
• 每次全排序：取最紧急 O(1)，但每次插入 O(n log n) 白花钱
• 有序结构：取最紧急 O(1)，但插入 O(n)
• 小顶堆：插入 O(log n)、取最紧急 O(1)、删除最紧急 O(log n)，紧凑数组、无指针、cache 友好

小顶堆的取舍本质是：用「部分有序」换取「插入和取最小都足够快」。React 调度器不需要一个完全有序的队列，它只需要随时知道「下一个最紧急的是谁」——这正是堆存在的意义。配合双键排序（sortIndex + id）、双队列（taskQueue/timerQueue）和 O(1) 的假删除取消，一个复杂的前端调度器，核心就是一个几十行的最小堆。