React 调度器优化：为什么我们要用“堆”来排队，而不是每次都“排序”？——一场关于 CPU 节约的深度解剖

大家好，我是你们的老朋友，今天咱们不聊组件怎么写，也不聊 Hooks 的坑，咱们来聊聊 React 最底层的那个“管家”——调度器。

在 React 的世界里，调度器就像是一个超级忙碌的餐厅经理。它手里拿着一份长长的“待办事项清单”（任务队列），上面写着各种任务，比如“渲染这个页面”、“更新这个状态”、“执行这个 Effect”。

问题来了，这个经理是个急性子，而且用户输入的速度极快，任务来得跟不要钱一样。于是，咱们面临一个经典的数据结构问题：如何高效地处理这个任务队列？

在很长一段时间里，或者说在 React 的早期版本里，那个“老派”的经理可能会选择一种最直观、最粗暴的方法：每次来了新任务，先把现有的清单全打乱，按优先级排个序，然后拿最上面的那个。

这种做法，我们叫它“排序数组”。

但后来，React 团队觉得这太浪费 CPU 了，于是他们换了个更聪明的工具：最小堆。

今天，咱们就剥开 React 源码的外衣，看看为什么 React 调度器要死磕这个“堆”，而不是用更简单的“排序”。

一、 “老派”作风的代价：每次都排序，累不累？

咱们先来模拟一下那个“老派”经理的工作流程。

假设你的任务队列里现在有 10 个任务。这些任务都有截止时间，比如 expirationTime。截止时间越早，优先级越高。

老派做法：

1. 用户输入了，来了个新任务 A。
2. 经理把任务 A 加到队尾，变成 11 个任务。
3. 经理大喊一声：“所有人停一下！”
4. 经理把 11 个任务全部拿出来，用 Array.sort() 重新排个序。
5. 经理拿走排在第一个（最早到期）的任务去执行。
6. 执行完了，再来个新任务 B……重复上述步骤。

听起来很合理，对吧？但这有个大问题：效率低得令人发指。

咱们来算笔账。假设你每秒要处理 100 次调度（这在现代 Web 应用中太常见了，想想用户疯狂点击按钮的场景）。

• 排序的时间复杂度是 O(N log N)。这就像是每次你要找队头，都要把整个队伍重新整一遍。
• 插入的时间复杂度是 O(1)（加到队尾），但查询时间复杂度变成了 O(N log N)（因为要排序）。

如果你的任务队列有 100 个任务，每次插入都要进行大约 100 * log(100) ≈ 660 次比较操作。每秒 100 次调度，就是每秒 66,000 次比较。这还没算上排序算法内部可能涉及的交换操作。

这就像什么呢？就像你点外卖，每次来了新订单，老板都要把店里所有的订单全部拿下来，按距离重新叠一遍，只为了找出离你最近的那一个。这老板要是还能活着，那一定是身强体壮。

React 的调度器可是要处理成千上万个 Fiber 节点的，如果每次都用排序，那 UI 渲染还没开始，CPU 就因为忙着排序而卡死了。

二、 “新派”智慧：最小堆的逻辑

那么，React 的调度器是怎么做的呢？它使用了最小堆。

听着很高级？其实没那么玄乎。最小堆本质上就是一个完全二叉树。

想象一下，你手里有一堆数字，你要把它们排好序，并且随时能取到最小的那个。如果你用数组，你需要排序。如果你用堆，你只需要保证一个规则：父节点的值总是小于或等于它的子节点。

这就好比一个等级森严的家族：爷爷最大，儿子们比爷爷小，孙子们比儿子们小。

为什么这能优化？

1. 插入（Push）： 不需要排序整个树，只需要把新元素放到树的最后，然后像“上浮”一样，跟它的父节点比较。如果它比父节点小，就交换位置。这个过程只需要 O(log N) 的时间。因为树的高度是 logN，你最多只需要往上走几层。
2. 取出（Pop）： 树的根节点（索引 1）永远是最小的那个元素。你直接拿走它就行！不需要遍历整个数组。取走根节点后，把最后一个元素移到根节点，然后像“下沉”一样，跟它的子节点比较，把小的那个换上去。这依然只需要 O(log N) 的时间。

所以，React 调度器的核心策略就是：插入 O(log N)，取出 O(1)。 这简直是针对高频插入场景的完美武器。

三、 源码深挖：React Scheduler 的堆实现

咱们直接看 React 源码（以 React 18 为例，packages/scheduler/src/SchedulerMinHeap.js）。

React 里的堆并不是一个复杂的类，它其实就是两个数组和一个计数器。

// 简化版 React 堆实现
const heap = [];
let heapSize = 0;

// 比较函数：判断 a 是否比 b 应该排在前面（a 的 expirationTime 更早）
function compare(a, b) {
  return a.expirationTime - b.expirationTime;
}

// 1. 插入任务
function push(heap, node) {
  const size = heapSize++;
  heap[size] = node;
  // 关键点：从最后开始，向上比较，直到找到合适的位置
  siftUp(heap, node, size);
}

function siftUp(heap, node, i) {
  let index = i;
  while (index > 0) {
    const parentIndex = (index - 1) >>> 1; // 父节点索引：(i-1)/2，使用位运算优化
    const parent = heap[parentIndex];
    // 如果当前节点比父节点小（优先级更高），就交换
    if (compare(node, parent) < 0) {
      heap[index] = parent;
      heap[parentIndex] = node;
      index = parentIndex;
    } else {
      break;
    }
  }
}

// 2. 取出任务
function pop(heap) {
  const first = heap[0]; // 拿走根节点（优先级最高的）
  const last = heap[heapSize - 1];
  heapSize--; // 队列减一
  if (heapSize > 0) {
    heap[0] = last; // 把最后一个元素移到根节点
    siftDown(heap, last, 0); // 关键点：从根节点开始，向下调整
  } else {
    // 如果队列为空，清空引用，防止内存泄漏
    heap[0] = null;
  }
  return first;
}

function siftDown(heap, node, i) {
  let index = i;
  const left = (2 * index) + 1; // 左子节点
  const right = (2 * index) + 2; // 右子节点
  let leftChild = heap[left];
  let rightChild = heap[right];

  // 逻辑：如果当前节点比左子节点大，且比右子节点也大，那它就站错了位置
  // 我们需要把最小的那个子节点“提拔”上来，自己“下沉”
  while (left < heapSize) {
    let leftIndex = left;
    let rightIndex = right;
    let child = leftChild;

    // 如果右子节点存在，且比左子节点小，那就选右子节点作为候选
    if (right < heapSize && compare(rightChild, leftChild) < 0) {
      leftIndex = right;
      rightIndex = left;
      child = rightChild;
    }

    // 比较当前节点和选出来的那个“小弟”谁更小
    if (compare(node, child) < 0) {
      // 如果自己更小，说明位置对了，不用动
      break;
    }

    // 否则，交换位置
    heap[index] = child;
    heap[leftIndex] = node;

    // 递归处理下一层
    index = leftIndex;
    left = (2 * index) + 1;
    right = (2 * index) + 2;
    leftChild = heap[left];
    rightChild = heap[right];
  }
}

看到没？这就是 React 调度器的核心。没有复杂的排序算法，只有简单的“上浮”和“下沉”。

四、 为什么不用普通的二叉树？——完全二叉树的重要性

你可能会问：“老师，普通的二叉树不也能存数据吗？”

普通的二叉树（比如 AVL 树或红黑树）虽然查找快，但它们为了保持平衡，插入和删除的操作极其复杂，涉及到大量的旋转。对于 React 这种每秒要进行成千上万次插入和删除的场景来说，旋转太重了。

React 选择的是完全二叉树。

什么是完全二叉树？就是除了最后一层，其他层都填满了，最后一层从左到右依次排列。

React 为什么喜欢完全二叉树？

1. 数组存储： 因为是完全二叉树，我们可以完美地用数组来存储它！不需要复杂的指针操作，也不需要维护左右子节点的引用。heap[1] 是根，heap[2] 是左孩子，heap[3] 是右孩子。
2. 索引计算简单： 父节点 i 的左孩子是 2*i，右孩子是 2*i + 1。这简直是数学家的福音，计算速度极快，没有任何额外开销。

五、 React 中的“花活儿”：startTime 与 expirationTime

React 的调度器不仅仅是插入和删除，它还有更复杂的逻辑：任务推迟。

React 不希望一次性把所有任务都塞给浏览器。它希望浏览器在空闲的时候干活，或者把紧急的任务插队到最前面。

这就引入了两个关键的时间概念：

1. startTime： 任务真正开始执行的时间。
2. expirationTime： 任务的截止时间（过期时间）。

React 的调度逻辑是这样的：

• 如果任务还没到 startTime，就把它扔到堆里，但是标记为“等待中”。
• 如果任务到了 expirationTime，就把它标记为“过期”，必须马上执行。
• 如果任务已经过期，或者当前时间 >= startTime，那就把它拿出来执行。

为什么这跟堆有关？

因为堆是基于 expirationTime 排序的。但是，如果你想在堆中间“插入”一个新任务，或者“删除”一个旧任务，排序数组做不到，但堆可以！

React 的 push 和 pop 操作，完美地支持了这种动态的优先级调整。

六、 深度剖析：交换逻辑的细节

咱们再仔细看看 siftUp 和 siftDown 的代码细节，这体现了 React 团队对性能的极致追求。

1. 索引计算：
const parentIndex = (index - 1) >>> 1;
这里用了无符号右移 >>>。为什么要用位运算？因为计算机处理位运算的速度比处理除法运算快得多。虽然在这个层面上差异微乎其微，但在调度器这种高频循环中，每一微秒都至关重要。

2. 比较函数：
if (compare(node, parent) < 0)
React 的比较函数非常简单：

function compare(a, b) {
  return a.expirationTime - b.expirationTime;
}

如果 a.expirationTime < b.expirationTime，说明 a 比 b 更紧急，应该排在前面。
注意，这里用的是减法。如果两个任务的 expirationTime 相同呢？React 会按照它们在队列中的顺序来（虽然这属于边界情况，但保证了稳定性）。

3. 循环终止条件：
在 siftUp 中，一旦 index <= 0，循环就结束了。这意味着新元素已经升到了根节点，或者它比根节点还大（这不太可能，除非你插入的是垃圾数据），反正它找到了位置。
在 siftDown 中，一旦 left >= heapSize，说明它已经是叶子节点了，不需要再下沉了。

七、 场景模拟：一场关于“输入法”的调度

为了让你彻底明白，咱们来模拟一个场景：你在输入框里疯狂打字。

时间 T0： 空队列。
时间 T1： 输入了字符 ‘A’。调度器创建任务 A，expirationTime = T1 + 5000ms。

• 操作： push(heap, A)。
• 过程： A 放在索引 0（数组下标 0）。计算父节点（索引 -1）。循环结束。堆里只有一个 A。
  时间 T2： 输入了字符 ‘B’。任务 B，expirationTime = T1 + 3000ms。
• 操作： push(heap, B)。
• 过程： B 放在索引 1。计算父节点是 A（索引 0）。比较：B 的截止时间比 A 早（3000 < 5000）。交换！
• 结果： A 在索引 1，B 在索引 0。
  时间 T3： 输入了字符 ‘C’。任务 C，expirationTime = T1 + 1000ms。
• 操作： push(heap, C)。
• 过程： C 放在索引 2。父节点是 B（索引 1）。比较：C 比 B 早。交换！
• 结果： B 在索引 2，C 在索引 1。
• 现在检查 C 的父节点： C 的父节点是 A（索引 0）。比较：C 比 A 早。交换！
• 最终结果： C 在索引 0，A 在索引 1，B 在索引 2。
  时间 T4： 浏览器空闲，准备调度。
• 操作： pop(heap)。
• 结果： 直接拿走索引 0 的 C。无需遍历！

如果是排序数组呢？

• 操作： 把 C 加到队尾，然后调用 sort()。
• 过程： 遍历所有元素，进行 O(N log N) 次比较和交换。
• 结果： 同样拿到了 C，但浪费了 CPU。

八、 React Scheduler 的“微操”：React 还做了什么？

除了用堆，React 的调度器在源码里还做了很多“微操”来配合这个堆结构。

1. 延迟执行：
React 不会每次 push 就立即去操作堆。有时候，如果当前时间还没到任务的 startTime，React 会直接忽略这个插入，或者把它放到一个“延迟列表”里。这大大减少了堆的维护压力。

2. 提前退出：
在 siftUp 和 siftDown 中，如果发现新任务的时间比当前队头的任务时间还晚，或者已经过期很久了，React 有时会选择不把它加入堆，或者直接丢弃。这取决于具体的调度策略（如 requestIdleCallback vs MessageChannel）。

3. 批量更新：
React 的堆不仅仅是存任务，它还处理“批处理”。如果你连续调用了三次 setState，React 不会触发三次调度，而是会把这三个任务合并成一个，或者把它们的截止时间统一推迟。这进一步减少了堆的操作次数。

九、 为什么不用优先队列？——堆就是优先队列

你可能会问：“既然堆这么好，为什么 React 不直接用现成的优先队列库，比如 PriorityQueue 或者 Java 的 PriorityQueue？”

因为 React 是用 JavaScript 写的（虽然底层有 Flow 类型检查）。JavaScript 没有原生的优先队列。

如果你用 JavaScript 实现一个优先队列，通常也就是封装一个堆。

React 的调度器甚至比普通的优先队列还要“变态”。普通的优先队列只关注“最小值”，而 React 的调度器关注的是时间窗口。

React 的调度器需要处理 startTime（何时开始）和 expirationTime（何时结束）。这意味着它需要频繁地修改堆中元素的优先级，或者根据时间窗口进行过滤。

普通的堆算法（如 Heapify）通常用于一次性构建堆，或者静态插入。React 需要的是动态的、高频的、基于时间维度的堆操作。

十、 总结：为什么是 Min-Heap？

好了，咱们总结一下。React 调度器使用最小堆而不是排序数组的根本原因，可以归纳为以下三点：

1. 极致的效率： 在高频操作（每秒成百上千次插入）下，堆的 O(log N) 插入和 O(1) 查询，对比排序数组的 O(N log N) 查询，性能差距是数量级的。React 必须保证主线程不被算法本身占用太多。
2. 完美的适配性： 堆的完全二叉树结构天然适合用数组存储，配合 React 的索引计算逻辑，能够极快地找到父节点和子节点。这种底层优化的代码，往往比封装好的类库更轻量、更可控。
3. 动态调度的需求： React 的调度不仅仅是“插入”和“取出”，它还涉及到基于时间（expirationTime）的动态优先级调整。堆结构允许我们在不重排整个队列的情况下，高效地插入和调整任务，这是排序数组做不到的。

结语

所以，下次当你看到 React 那个复杂的调度器源码，看到那一堆关于 heap、siftUp、siftDown 的函数时，不要觉得它晦涩难懂。

你可以把它想象成一个极其自律的图书管理员，他手里拿着一个二叉树结构的架子。新书来了，他不需要把整排书都搬下来重新排，他只需要把新书插到正确的位置，或者把最旧的书取下来。

这种对资源的极致节约，正是 React 能够在复杂的单线程 JavaScript 环境中，依然保持流畅动画和高性能渲染的秘密武器。

这就是为什么我们要用堆，而不是排序。因为在这个分秒必争的浏览器世界里，聪明，就是省钱。