二叉树

二叉树（Binary tree），每个节点最多只有两个分支的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

完全二叉树

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）

以下都是完全二叉树：

二叉堆

二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”（max heap）。

当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”（min heap）。

最小堆

今天我们只讲最小堆（min heap）。因为 React 的任务列表（taskQueue）用的就是最小堆。

React 用的是数组结构表示的最小堆，一张图带你明白最小堆如何映射为数组：

React 采用原因

React 为什么采用最小堆结构呢？

这是因为在最小堆结构中，最小值就在第一个，React 可以快速的取出最小值。

React 为什么要取出最小值而不是最大值呢？我们可以这样设想，React 将更新任务拆成多个小任务，每个小任务的数据结构是一个带着 expirationTime 的对象，expirationTime 表示这个任务的过期时间，expirationTime 越小就表示过期时间越近，该任务的优先级就越高，取出最小值就相当于取出优先级最高的任务。

React 函数实现

React 的最小堆涉及 5 个函数：

push，往最小堆插入新节点
pop，删除根节点，就是那个最小的值
siftUp，上浮，不停地交换节点和父节点
shiftDown，下沉，不停地交换节点和子节点
peek，获取根节点，也就是数组的第一个元素，也就是优先级最高的那个任务

接下来我们进行详细的讲解。

插入过程（push）

我们先讲二叉堆的插入过程：

当插入一个新节点的时候，我们会在二叉堆的最后添加，然后将其“上浮”到正确位置。举个例子：

我们尝试在下面这个二叉堆中，插入新节点，它的值为 1，我们会将这个值与父节点的值进行对比，如果小于父节点，就交换两个节点，就这样不断比较上浮，直到父节点比它小

React 的实现代码如下：

// 源码地址：https://github.com/facebook/react/blob/main/packages/scheduler/src/SchedulerMinHeap.js
function push(heap, node) {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}
function siftUp(heap, 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) {
  // 首先比较 sortIndex，其次是 id
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}
// 测试代码
let taskQueue = [{sortIndex: 2}, {sortIndex: 7}, {sortIndex: 5}, {sortIndex: 12}, {sortIndex: 22}, {sortIndex: 17}];
push(taskQueue, {sortIndex: 1})
console.log(JSON.stringify(taskQueue))

>>> 1

这个实现过程中，可能不熟悉的是这句：

const parentIndex = (index - 1) >>> 1;

这是用来获取父节点的索引值的。

我们先看下 >>> 这个运算符，引用 MDN 的介绍：

无符号右移运算符（>>>）（零填充右移）将左操作数计算为无符号数，并将该数字的二进制表示形式移位为右操作数指定的位数，取模 32。向右移动的多余位将被丢弃，零位从左移入。其符号位变为 0，因此结果始终为非负数。与其他按位运算符不同，零填充右移返回一个无符号 32 位整数。

看起来有些复杂？没关系，我们直接讲过程，我们以 5 >>> 1为例：

首先将 5 转为 32 位的二进制数：00000000000000000000000000000101。

>>> 1表示将该二进制向右移动 1 位，向右移动出去的被丢弃，左边部零，于是变成了0000000000000000000000000000010，换算成十进制，就是 2，所以 5 >>> 1的结果就是 2。

我们再举一个例子，4 >>> 1，4 是 00000000000000000000000000000101，向右移动一位变成 0000000000000000000000000000010，换算成十进制，就是 2，所以 4 >>> 1的结果也是 2。

我们再试几个例子：

所以你可以简单理解为，x >>> 1表示的就是除以 2 后取整。

我们再看下最小堆和数组的映射图：

你看父节点的索引值是不是就是 (子节点的索引值 - 1) / 2 后取整。

删除过程（pop）

现在我们来看删除过程，因为我们删除的是根节点，它的具体流程是：

取出最后一个节点，替换掉根节点
将节点“下沉”到正确位置

我们举个例子：

现在我们要删除根节点 2 ，我们将最后一个节点 25，替换掉根节点 2，然后将新的根节点 25，与两个子节点进行比较，将节点与更小的那个子节点进行交换，然后这样不断比较下沉，直到子节点都比它大。

它的具体实现如下：

// 源码地址：https://github.com/facebook/react/blob/main/packages/scheduler/src/SchedulerMinHeap.js
function pop(heap) {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  // JavaScript 的 pop 方法删除并返回数组的最后一个元素
  const last = heap.pop();
  if (last !== first) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }
  return first;
}
function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  const halfLength = length >>> 1;
  while (index < halfLength) {
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];
    // 如果 left 比 node 小
    if (compare(left, node) < 0) {
      // 如果 right 比 left 还小，说明 right 最小，right 与 node 交换
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      }
      // 说明 left 最小，left 与 node 交换
      else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    }
    // 如果 left node 大，但 right 比 node 小，right 与 node 交换
    else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // 子元素都比 node 大
      return;
    }
  }
}
// 示例代码
let taskQueue = [{sortIndex: 2}, {sortIndex: 5}, {sortIndex: 7}, {sortIndex: 12}, {sortIndex: 22}, {sortIndex: 17}, {sortIndex: 25}];
pop(taskQueue)
// [{"sortIndex":5},{"sortIndex":12},{"sortIndex":7},{"sortIndex":25},{"sortIndex":22},{"sortIndex":17}]
console.log(JSON.stringify(taskQueue))

halfLength

siftDown 的实现中，我认为最有意思是在 halfLength 这里：

  const length = heap.length;
  const halfLength = length >>> 1;
  while (index < halfLength) {//...}

实际上 React 这里之前直接用的 index < length 而非 index < halfLength，我们可以查看当时的提交记录：

那为什么只用比较一半就可以了呢？如果我们尝试自己去画几个最小堆，发现也确实如此，完全不用全部比较一遍。如果非要从算术的角度来看的话，我们可以这样想：假设父节点的 index 为 x，那么左子节点的 index 为 2x + 1，右子节点的 index 为 2x + 2，每一次 shiftDown，index 的最大变化就是 2x + 2，而 2x + 2 最大只能等于 length - 1，那么：

因为 2x + 2 <= length - 1 
所以 x <= length/2 - 1.5
我们知道 y >>> 1 ，在 y 为正数的情况下，计算的结果为 y/2 - 0.5 或者 y/2
如果 x <= length/2 - 1.5
那么肯定 x < length/2 - 0.5 以及 x < length/2
所以肯定 x < length >>> 1

peek

除此之外，还有一个 peek 方法，获取数组的第一个元素：

function peek(heap) {
  return heap.length === 0 ? null : heap[0];
}

好了，React 的 SchedulerMinHeap.js 这个文件的所有代码就正式讲完了，它是一个几乎完全独立的实现，当然 Scheduler 也是独立的，下篇我们接着讲 Scheduler。

React 之最小堆（min heap）

二叉树