React 之最小堆min heap圖文詳解

2022-11-23 14:00:19

二元樹

二元樹（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圖文詳解的詳細內容，更多關於React最小堆min heap的資料請關注it145.com其它相關文章！