二叉樹

二叉樹（Binary tree），每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”。二叉樹的分支具有左右次序，不能隨意顛倒。

完全二叉樹

在一顆二叉樹中，若除最后一層外的其余層都是滿的，并且最后一層要么是滿的，要么在右邊缺少連續(xù)若干節(jié)點(diǎn)，則此二叉樹為完全二叉樹（Complete Binary Tree）

以下都是完全二叉樹：

二叉堆

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

二叉堆滿足堆特性：父節(jié)點(diǎn)的鍵值總是保持固定的序關(guān)系于任何一個(gè)子節(jié)點(diǎn)的鍵值，且每個(gè)節(jié)點(diǎn)的左子樹和右子樹都是一個(gè)二叉堆。

當(dāng)父節(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為“最大堆”（max heap）。

當(dāng)父節(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為“最小堆”（min heap）。

最小堆

今天我們只講最小堆（min heap）。因?yàn)?React 的任務(wù)列表（taskQueue）用的就是最小堆。

React 用的是數(shù)組結(jié)構(gòu)表示的最小堆，一張圖帶你明白最小堆如何映射為數(shù)組：

React 采用原因

React 為什么采用最小堆結(jié)構(gòu)呢？

這是因?yàn)樵谧钚《呀Y(jié)構(gòu)中，最小值就在第一個(gè)，React 可以快速的取出最小值。

React 為什么要取出最小值而不是最大值呢？我們可以這樣設(shè)想，React 將更新任務(wù)拆成多個(gè)小任務(wù)，每個(gè)小任務(wù)的數(shù)據(jù)結(jié)構(gòu)是一個(gè)帶著 expirationTime 的對(duì)象，expirationTime 表示這個(gè)任務(wù)的過期時(shí)間，expirationTime 越小就表示過期時(shí)間越近，該任務(wù)的優(yōu)先級(jí)就越高，取出最小值就相當(dāng)于取出優(yōu)先級(jí)最高的任務(wù)。

React 函數(shù)實(shí)現(xiàn)

React 的最小堆涉及 5 個(gè)函數(shù)：

• push，往最小堆插入新節(jié)點(diǎn)
• pop，刪除根節(jié)點(diǎn)，就是那個(gè)最小的值
• siftUp，上浮，不停地交換節(jié)點(diǎn)和父節(jié)點(diǎn)
• shiftDown，下沉，不停地交換節(jié)點(diǎn)和子節(jié)點(diǎn)
• peek，獲取根節(jié)點(diǎn)，也就是數(shù)組的第一個(gè)元素，也就是優(yōu)先級(jí)最高的那個(gè)任務(wù)

接下來我們進(jìn)行詳細(xì)的講解。

插入過程（push）

我們先講二叉堆的插入過程：

當(dāng)插入一個(gè)新節(jié)點(diǎn)的時(shí)候，我們會(huì)在二叉堆的最后添加，然后將其“上浮”到正確位置。舉個(gè)例子：

我們嘗試在下面這個(gè)二叉堆中，插入新節(jié)點(diǎn)，它的值為 1，我們會(huì)將這個(gè)值與父節(jié)點(diǎn)的值進(jìn)行對(duì)比，如果小于父節(jié)點(diǎn)，就交換兩個(gè)節(jié)點(diǎn)，就這樣不斷比較上浮，直到父節(jié)點(diǎn)比它小

React 的實(shí)現(xiàn)代碼如下：

// 源碼地址：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) {
    // 獲取父節(jié)點(diǎn)的索引位置
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // 如果父節(jié)點(diǎn)更大，就交換位置
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // 直到父節(jié)點(diǎn)更小，就退出
      return;
    }
  }
}
function compare(a, b) {
  // 首先比較 sortIndex，其次是 id
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}
// 測(cè)試代碼
let taskQueue = [{sortIndex: 2}, {sortIndex: 7}, {sortIndex: 5}, {sortIndex: 12}, {sortIndex: 22}, {sortIndex: 17}];
push(taskQueue, {sortIndex: 1})
console.log(JSON.stringify(taskQueue))

>>> 1

這個(gè)實(shí)現(xiàn)過程中，可能不熟悉的是這句：

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

這是用來獲取父節(jié)點(diǎn)的索引值的。

我們先看下 >>> 這個(gè)運(yùn)算符，引用 MDN 的介紹：

無符號(hào)右移運(yùn)算符（>>>）（零填充右移）將左操作數(shù)計(jì)算為無符號(hào)數(shù)，并將該數(shù)字的二進(jìn)制表示形式移位為右操作數(shù)指定的位數(shù)，取模 32。向右移動(dòng)的多余位將被丟棄，零位從左移入。其符號(hào)位變?yōu)?0，因此結(jié)果始終為非負(fù)數(shù)。與其他按位運(yùn)算符不同，零填充右移返回一個(gè)無符號(hào) 32 位整數(shù)。

看起來有些復(fù)雜？沒關(guān)系，我們直接講過程，我們以 5 >>> 1為例：

首先將 5 轉(zhuǎn)為 32 位的二進(jìn)制數(shù)：00000000000000000000000000000101。

>>> 1表示將該二進(jìn)制向右移動(dòng) 1 位，向右移動(dòng)出去的被丟棄，左邊部零，于是變成了0000000000000000000000000000010，換算成十進(jìn)制，就是 2，所以 5 >>> 1的結(jié)果就是 2。

我們?cè)倥e一個(gè)例子，4 >>> 1，4 是 00000000000000000000000000000101，向右移動(dòng)一位變成 0000000000000000000000000000010，換算成十進(jìn)制，就是 2，所以 4 >>> 1的結(jié)果也是 2。

我們?cè)僭噹讉€(gè)例子：

所以你可以簡(jiǎn)單理解為，x >>> 1表示的就是除以 2 后取整。

我們?cè)倏聪伦钚《押蛿?shù)組的映射圖：

你看父節(jié)點(diǎn)的索引值是不是就是 (子節(jié)點(diǎn)的索引值 - 1) / 2 后取整。

刪除過程（pop）

現(xiàn)在我們來看刪除過程，因?yàn)槲覀儎h除的是根節(jié)點(diǎn)，它的具體流程是：

• 取出最后一個(gè)節(jié)點(diǎn)，替換掉根節(jié)點(diǎn)
• 將節(jié)點(diǎn)“下沉”到正確位置

我們舉個(gè)例子：

現(xiàn)在我們要?jiǎng)h除根節(jié)點(diǎn) 2 ，我們將最后一個(gè)節(jié)點(diǎn) 25，替換掉根節(jié)點(diǎn) 2，然后將新的根節(jié)點(diǎn) 25，與兩個(gè)子節(jié)點(diǎn)進(jìn)行比較，將節(jié)點(diǎn)與更小的那個(gè)子節(jié)點(diǎn)進(jìn)行交換，然后這樣不斷比較下沉，直到子節(jié)點(diǎn)都比它大。

它的具體實(shí)現(xiàn)如下：

// 源碼地址：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 方法刪除并返回?cái)?shù)組的最后一個(gè)元素
  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 的實(shí)現(xiàn)中，我認(rèn)為最有意思是在 halfLength 這里：

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

實(shí)際上 React 這里之前直接用的 index < length 而非 index < halfLength，我們可以查看當(dāng)時(shí)的提交記錄：

那為什么只用比較一半就可以了呢？如果我們嘗試自己去畫幾個(gè)最小堆，發(fā)現(xiàn)也確實(shí)如此，完全不用全部比較一遍。 如果非要從算術(shù)的角度來看的話，我們可以這樣想： 假設(shè)父節(jié)點(diǎn)的 index 為 x，那么左子節(jié)點(diǎn)的 index 為 2x + 1，右子節(jié)點(diǎn)的 index 為 2x + 2，每一次 shiftDown，index 的最大變化就是 2x + 2，而 2x + 2 最大只能等于 length - 1，那么：

因?yàn)?2x + 2 <= length - 1 
所以 x <= length/2 - 1.5

我們知道 y >>> 1 ，在 y 為正數(shù)的情況下，計(jì)算的結(jié)果為 y/2 - 0.5 或者 y/2

如果 x <= length/2 - 1.5
那么肯定 x < length/2 - 0.5 以及 x < length/2
所以肯定 x < length >>> 1

peek

除此之外，還有一個(gè) peek 方法，獲取數(shù)組的第一個(gè)元素：

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

好了，React 的 SchedulerMinHeap.js 這個(gè)文件的所有代碼就正式講完了，它是一個(gè)幾乎完全獨(dú)立的實(shí)現(xiàn)，當(dāng)然 Scheduler 也是獨(dú)立的，下篇我們接著講 Scheduler

以上就是React 之最小堆min heap圖文詳解的詳細(xì)內(nèi)容，更多關(guān)于React最小堆min heap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論