关于前端:结合React源码五分钟带你掌握优先队列

这是第 85 篇不掺水的原创，想获取更多原创好文，请搜寻公众号关注咱们吧~ 本文首发于政采云前端博客：联合 React 源码，五分钟带你把握优先队列

前言

最近写一个需要用到了优先队列和二叉堆的相干常识，借此机会梳理了一些二叉堆的相干常识分享给大家。

什么是优先队列

优先队列是数据结构中的根底概念，与队列先进先出（FIFO）的出队程序不同的是，它的出队程序与元素的优先级相干。

例如 React 的工夫分片（React Fiber），它将渲染工作分了优先级，出队的程序与工作的“重要水平”存在关系，那么满足这种状况的数据结构就是 优先队列 。

优先队列的操作

• 插入：在优先队列中插入元素，并使队列“有序”
• 删除最大 / 最小值：删除并返回最大 / 最小的元素，并使队列“有序”
• 查找最大 / 最小关键字：查找最大 / 最小的值

优先队列的实现比拟

优先队列能够由以上多种形式实现，而优先队列的次要操作是插入和删除，其中二叉搜寻树和二叉堆这两项操作的工夫复杂度均为 logn , 但二叉树在屡次删除之后容易导致树的歪斜，同时查找老本也高于二叉堆，所以最终二叉堆是比拟合乎实现优先队列的数据结构。

二叉堆

在二叉堆中数组中，要保障每个元素都小于（大于）或等于另外两个特定地位的元素。例如下图的树中，父节点总是小于或等于子节点。

对于二叉堆有如下性质：

• 节点 k 的父节点下标为 k / 2（向下取整）
• 已某节点为根节点的子树，该节点是这颗树的极值

二叉堆的操作

插入

二叉堆的插入非常简单，只须要在二叉堆的最初增加要插入的内容，并将其“上浮”到正确地位。

尝试在下面的二叉堆中插入新元素 9，过程如下：

在尾部插入元素 9，与父节点进行比照，有序性被毁坏，与父元素替换地位。

替换胜利后，持续上一轮操作，与父节点进行比照，依然无奈满足有序性，持续调换地位。

再次替换后合乎。

程序框架

function push {
  * 在堆尾部增加元素
  * 执行上浮循环
    * 与父元素对比大小，将较大的放在父节点地位
  
  return minItem
}

实现

function push(heap: Heap, node: Node): void {
  const index = heap.length;
  heap.push(node); // 在堆尾部增加元素
  siftUp(heap, node, index); // 进行上浮操作
}

function siftUp(heap, node, i) {
  let index = i;
  while (true) {const parentIndex = (index - 1) >>> 1; // 父节点地位：parentIndex = childIndex / 2
    const parent = heap[parentIndex];
    if (parent !== undefined && compare(parent, node) > 0) {
      // The parent is larger. Swap positions.
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // The parent is smaller. Exit.
      return;
    }
  }
}

删除

取出根节点的值比照插入略微简单一点，归纳起来能够分为三步：

1. 取出根节点的值
2. 将最初一个元素与根节点进行替换，并删除最初一个元素
3. 下沉

取出根节点。

将最初一个元素与根节点调换，并删除。比照发现有序性被毁坏，进行对调。

实现删除。

程序框架

function pop {
  * 设定 minItem 保留根节点
  * 取出最初一个节点与根节点替换，并删除最初一个节点
  * 执行下沉循环
    * 将根元素与左右子节点比照, 筛选较小的与父节点替换地位
  
  return minItem
}

实现

export function pop(heap: Heap): Node | null {const first = heap[0]; // 取出根节点
  if (first !== undefined) {const last = heap.pop(); // 取出最初一位元素，并删除
    if (last !== first) {heap[0] = last; // 与根节点对调
      siftDown(heap, last, 0); // 下沉
    }
    return first;
  } else {return null;}
}

function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  while (index < length) {const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];

    // If the left or right node is smaller, swap with the smaller of those.
    // 寻找左右儿子较小的那一个替换
    if (left !== undefined && compare(left, node) < 0) { // 左子节点小于根节点
      if (right !== undefined && compare(right, left) < 0) {heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (right !== undefined && compare(right, node) < 0) { // 左子节点大于根节点，右子节点小于根节点
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // Neither child is smaller. Exit.
      return;
    }
  }
}

以下是 react 源码中 scheduler/src/SchedulerMinHeap.js 对于最小堆的残缺实现：

/**
 * Copyright (c) Facebook, Inc. and its affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *
 * @flow strict
 */

// 定义最小堆极其元素，其中 sortIndex 为最小堆比照的 key，若 sortIndex 雷同，则比照 id
type Heap = Array<Node>;
type Node = {|
  id: number,
  sortIndex: number,
|};

// 入队操作，在入队实现之后进行“上浮”export function push(heap: Heap, node: Node): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

// 查找最大值
export function peek(heap: Heap): Node | null {const first = heap[0];
  return first === undefined ? null : first;
}

// 删除并返回最大值
export function pop(heap: Heap): Node | null {const first = heap[0]; // 取出根节点（哨兵）if (first !== undefined) {const last = heap.pop(); // 取出最初一位元素，并删除
    if (last !== first) { // 头尾并没有对撞
      heap[0] = last; // 与根节点对调
      siftDown(heap, last, 0); // 下沉
    }
    return first;
  } else {return null;}
}

// 上浮，调整树结构
function siftUp(heap, node, i) {
  let index = i;
  while (true) {const parentIndex = (index - 1) >>> 1; // 父节点地位：parentIndex = childIndex / 2，此处应用位操作，右移一位
    const parent = heap[parentIndex];
    if (parent !== undefined && compare(parent, node) > 0) { // 比照父节点和子元素的大小
      // The parent is larger. Swap positions.
      heap[parentIndex] = node; // 若父节点较大，则更换地位
      heap[index] = parent;
      index = parentIndex;
    } else {
      // The parent is smaller. Exit.
      return;
    }
  }
}

// 下沉，调整树结构
function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  while (index < length) {const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];

    // If the left or right node is smaller, swap with the smaller of those.
    // 寻找左右儿子较小的那一个替换
    if (left !== undefined && compare(left, node) < 0) {if (right !== undefined && compare(right, left) < 0) { // 左子节点小于根节点
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (right !== undefined && compare(right, node) < 0) { // 左子节点大于根节点，右子节点小于根节点
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // Neither child is smaller. Exit.
      return;
    }
  }
}

function compare(a, b) {
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

堆排序

利用最大 / 最小堆的个性，咱们很容易就能实现对数组的排序，反复执行 pop 就能进行升序排列，如果要降序，应用最大堆即可，该操作工夫复杂度为 nlogn。

多叉堆

为了谋求更优的工夫复杂度，咱们能够将二叉堆改为多叉堆实现，下图为一个三叉堆：

与二叉堆不同的是对于含有 N 个元素的 d 叉堆（通常状况下 d >= 2），随着 d 的减少，树高 K = logdN 的斜率会降落，然而 d 越大，删除操作的老本会更高。所以子元素不是越多越好，通常状况下三叉堆和四叉堆的利用会比拟常见。

在 libev 中有这么一段正文 https://github.com/enki/libev…，他提及了四叉树相比二叉堆来说缓存更加敌对。依据 benchmark，在 50000+ 个 watchers 的场景下，四叉树会有 5% 的性能劣势。

/*
 * at the moment we allow libev the luxury of two heaps,
 * a small-code-size 2-heap one and a ~1.5kb larger 4-heap
 * which is more cache-efficient.
 * the difference is about 5% with 50000+ watchers.
 */

同样 Go 语言中的定时器的 timersBucket 的数据结构也采纳了最小四叉堆。

结语

多叉堆，例如四叉堆更加适宜数据量大，对缓存要求敌对对场景。二叉堆实用数据量比拟小且频繁插入和删除的场景。通常状况下二叉堆能够满足大部分状况下的需要，如果编写底层代码，并且对性能有更高的要求，那么能够思考多叉堆实现优先队列。

举荐浏览

编写高质量可保护的代码：Awesome TypeScript

编写高质量可保护的代码：组件的形象与粒度

招贤纳士

政采云前端团队（ZooTeam），一个年老富裕激情和创造力的前端团队，隶属于政采云产品研发部，Base 在风景如画的杭州。团队现有 40 余个前端小伙伴，平均年龄 27 岁，近 3 成是全栈工程师，妥妥的青年风暴团。成员形成既有来自于阿里、网易的“老”兵，也有浙大、中科大、杭电等校的应届新人。团队在日常的业务对接之外，还在物料体系、工程平台、搭建平台、性能体验、云端利用、数据分析及可视化等方向进行技术摸索和实战，推动并落地了一系列的外部技术产品，继续摸索前端技术体系的新边界。

如果你想扭转始终被事折腾，心愿开始能折腾事；如果你想扭转始终被告诫须要多些想法，却无从破局；如果你想扭转你有能力去做成那个后果，却不须要你；如果你想扭转你想做成的事须要一个团队去撑持，但没你带人的地位；如果你想扭转既定的节奏，将会是“5 年工作工夫 3 年工作教训”；如果你想扭转原本悟性不错，但总是有那一层窗户纸的含糊… 如果你置信置信的力量，置信平凡人能成就不凡事，置信能遇到更好的本人。如果你心愿参加到随着业务腾飞的过程，亲手推动一个有着深刻的业务了解、欠缺的技术体系、技术发明价值、影响力外溢的前端团队的成长历程，我感觉咱们该聊聊。任何工夫，等着你写点什么，发给 ZooTeam@cai-inc.com