二叉樹

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

完全二叉樹

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

以下都是完全二叉樹：

二叉堆

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

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

當父節(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為“最大堆”（max heap）。

當父節(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為“最小堆”（min heap）。

最小堆

今天我們只講最小堆（min heap）。因為 React 的任務列表（taskQueue）用的就是最小堆。

React 用的是數組結構表示的最小堆，一張圖帶你明白最小堆如何映射為數組：

React 采用原因

React 為什么采用最小堆結構呢？

這是因為在最小堆結構中，最小值就在第一個，React 可以快速的取出最小值。

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

React 函數實現

React 的最小堆涉及 5 個函數：

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

接下來我們進行詳細的講解。

插入過程（push）

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

當插入一個新節(jié)點的時候，我們會在二叉堆的最后添加，然后將其“上浮”到正確位置。舉個例子：

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

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) {
    // 獲取父節(jié)點的索引位置
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // 如果父節(jié)點更大，就交換位置
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // 直到父節(jié)點更小，就退出
      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;

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

我們先看下 >>> 這個運算符，引用 MDN 的介紹：

無符號右移運算符（>>>）（零填充右移）將左操作數計算為無符號數，并將該數字的二進制表示形式移位為右操作數指定的位數，取模 32。向右移動的多余位將被丟棄，零位從左移入。其符號位變?yōu)?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 后取整。

我們再看下最小堆和數組的映射圖：

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

刪除過程（pop）

現在我們來看刪除過程，因為我們刪除的是根節(jié)點，它的具體流程是：

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

我們舉個例子：

現在我們要刪除根節(jié)點 2 ，我們將最后一個節(jié)點 25，替換掉根節(jié)點 2，然后將新的根節(jié)點 25，與兩個子節(jié)點進行比較，將節(jié)點與更小的那個子節(jié)點進行交換，然后這樣不斷比較下沉，直到子節(jié)點都比它大。

它的具體實現如下：

// 源碼地址：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，我們可以查看當時的提交記錄：

那為什么只用比較一半就可以了呢？如果我們嘗試自己去畫幾個最小堆，發(fā)現也確實如此，完全不用全部比較一遍。 如果非要從算術的角度來看的話，我們可以這樣想： 假設父節(jié)點的 index 為 x，那么左子節(jié)點的 index 為 2x + 1，右子節(jié)點的 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圖文詳解的詳細內容，更多關于React最小堆min heap的資料請關注腳本之家其它相關文章！

最新評論