理解 React Scheduler 最小堆

[FE-Sadhu]

为什么用最小堆？

React 的需求

React 的 Scheduler 模块做的工作就是调度注册好的优先级任务，也就是做了如下两件事：

1. 提供注册优先级任务的方法
2. 调度优先级任务执行

使用者可以随时注册任意优先级的任务，Scheduler 每次调度执行的是最高优先级任务。

对于 React 而言，把更新任务拆成了一个个小任务，每个小任务的数据结构包含 expirationTime 字段，表示这个任务的过期时间，expirationTime 越小就表示过期时间越近，该任务的优先级就越高。所以 Scheduler 在每次调度时取出最小值就相当于取出优先级最高的任务。

React 时间分片期望是每帧都有一点时间去执行这些小任务，所以 Scheduler 每帧都会调度一下最高优先级任务执行，取出优先级任务的频次是很高的，相对来说注册优先级任务往往是有新的更新发生时才会注册，频次比较低。

如果你来实现，会怎么去管理一众优先级任务呢 ？

常规思路：用数组保存优先级任务，每次注册任务时就往数组 push，每次取出时，遍历取出最小值。

const list = [];
// 时间复杂度 O(1);
function push(task) {
  list.push(task);
}

function pop(task) {
  // 好时 O(1)，坏时 O(n)
  const index = list.indexOf(task);
  // 好时 O(1)，坏时 O(n)
  list.splice(index, 1);
}

function getTask() {
  if (!list.length) {
    return;
  }
  // O(n)
  return list.reduce((prev, curr) => { 
    return curr.expirationTime < prev.expirationTime ? curr : prev;
  }, { expirationTime: Infinity})
}

以上这个实现可以满足需求，但是性能不利于「高频取、低频插」。

你可能想着在插入时从小到大 sort 一下 list，然后取的时候直接取第一个元素就行。这样变成了 「取 O(1)」「插 O(nlogn)」。从性能角度来讲这样会比以上实现要更适合 React 的需求。

但是还可以再进一步，如果用最小堆的话，可以达到 「取 O(1)」「插 O(logn)」的性能。

堆的特性

• 符合完全二叉树
• 父节点的键值总是小于（大于）或等于任何一个子节点的键值

若是父节点的键值总是小于或等于任何一个子节点的键值，那么就是最小堆，否则是最大堆。

用数组来保存各个节点，有个规律就是：下标为 i 的节点的子节点是 2i + 1 与 2i + 2。

很简单地能推出父节点的下标是 : Math.floor(i - 1)/2 等同于 (i - 1) >>> 1。

看不明白这规律和位运算的，草稿纸推演几遍。

最小堆的实现

这版实现其实和 React 的大差不差了，看懂这个就懂了 React 最小堆的实现

const heap = [];

// 取小值，O(1)
function peek() {
  return heap.length === 0 ? null : heap[0];
}

// 插入一个节点
function push(node) {
  const index = heap.length;
  // 添加在数组最后面  O(1)
  heap.push(node);
  // 上浮至对应位置 O(logn)
  siftUp(node, index);
}

function siftUp(node, i) {
  let index = i;
  while (index > 0) {
    // 找到父节点索引
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    // 比较当前节点与父节点的大小
    if (compare(parent, node) > 0) {
      // 若更大，交换位置
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // 若更小，上浮完成
      return;
    }
  }
}

function compare(a, b) {
  // 假设 .value 就是该节点的值
  return a.value - b.value
}

// 剔除最后第一个节点
function pop() {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  // O(1)
  const last = heap.pop();
  if (last !== first) {
    // 最后一个节点与第一个节点交换
    heap[0] = last;
    // 下沉至对应位置 O(logn)
    siftDown(last, 0);
  }
  return first;
}

function siftDown(node, i) {
  let index = i;
  const length = heap.length;
  const halfLength = length >>> 1;
  // 为什么比较一半就行，见下推理过程：
  // 每次变化，索引最大变为 2i + 2，肯定是小于等于 length - 1 的。
  // 2i + 2 <= length - 1   -->   i <= (length - 3) / 2;
  // --> i < length / 2  --> 近似于 i < length >>> 1
  // 其实这里 < length 也没问题，React 初版也是这么实现的
  while (index < halfLength) {
    // 左节点索引是 2i + 1
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    // 右节点是 2i + 2
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];

    // 如果当前节点比左节点更小
    if (compare(left, node) < 0) {
      // 并且右节点 < 左节点
      if (rightIndex < length && compare(right, left) < 0) {
        // 交换更小的右节点与当前节点
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        // 交换更小的左节点和当前节点
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    // 如果比右节点更小，交换右节点
    } else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // 没有子节点
      return;
    }
  }
}