欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

React?之最小堆min?heap圖文詳解

 更新時(shí)間:2022年11月22日 11:56:47   作者:冴羽  
這篇文章主要為大家介紹了React?之最小堆min?heap圖文詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

二叉樹(shù)

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

完全二叉樹(shù)

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

以下都是完全二叉樹(shù):

二叉堆

二叉堆(binary heap)是一種特殊的堆,二叉堆是完全二叉樹(shù)或者是近似完全二叉樹(shù)。

二叉堆滿足堆特性:父節(jié)點(diǎn)的鍵值總是保持固定的序關(guān)系于任何一個(gè)子節(jié)點(diǎn)的鍵值,且每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是一個(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ù)的過(guò)期時(shí)間,expirationTime 越小就表示過(guò)期時(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ù)

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

插入過(guò)程(push)

我們先講二叉堆的插入過(guò)程:

當(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)過(guò)程中,可能不熟悉的是這句:

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

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

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

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

看起來(lái)有些復(fù)雜?沒(méi)關(guān)系,我們直接講過(guò)程,我們以 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 后取整。

刪除過(guò)程(pop)

現(xiàn)在我們來(lái)看刪除過(guò)程,因?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 還小,說(shuō)明 right 最小,right 與 node 交換
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      }
      // 說(shuō)明 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í)的提交記錄

那為什么只用比較一半就可以了呢?如果我們嘗試自己去畫(huà)幾個(gè)最小堆,發(fā)現(xiàn)也確實(shí)如此,完全不用全部比較一遍。 如果非要從算術(shù)的角度來(lái)看的話,我們可以這樣想: 假設(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)文章!

相關(guān)文章

  • react實(shí)現(xiàn)路由攔截的示例代碼

    react實(shí)現(xiàn)路由攔截的示例代碼

    這篇文章主要介紹react實(shí)現(xiàn)路由攔截的,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2024-02-02
  • 淺談React 服務(wù)器端渲染的使用

    淺談React 服務(wù)器端渲染的使用

    本篇文章主要介紹了淺談React 服務(wù)器端渲染的使用,React是最受歡迎的客戶端 JavaScript 框架,在本教程中,我們將逐步向您介紹服務(wù)器端的渲染示例
    2018-05-05
  • 詳解React中的useMemo和useCallback的區(qū)別

    詳解React中的useMemo和useCallback的區(qū)別

    React中的useMemo和useCallback是兩個(gè)重要的Hooks。常常被用于優(yōu)化組件的性能。雖然這兩個(gè)Hooks看起來(lái)很相似,但它們彼此之間還是有很大的區(qū)別的,隨著小編一起來(lái)學(xué)習(xí)吧
    2023-04-04
  • React中使用react-json-view展示JSON數(shù)據(jù)的操作方法

    React中使用react-json-view展示JSON數(shù)據(jù)的操作方法

    react-json-view是一個(gè)用于顯示和編輯javascript數(shù)組和JSON對(duì)象的React組件,本文給大家分享React中使用react-json-view展示JSON數(shù)據(jù)的操作方法,感興趣的朋友一起看看吧
    2023-12-12
  • react 創(chuàng)建單例組件的方法

    react 創(chuàng)建單例組件的方法

    這篇文章主要介紹了react 創(chuàng)建單例組件的方法,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2018-04-04
  • react性能優(yōu)化達(dá)到最大化的方法 immutable.js使用的必要性

    react性能優(yōu)化達(dá)到最大化的方法 immutable.js使用的必要性

    這篇文章主要為大家詳細(xì)介紹了react性能優(yōu)化達(dá)到最大化的方法,一步一步優(yōu)化react性能的過(guò)程,告訴大家使用immutable.js的必要性,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-03-03
  • React中關(guān)于render()的用法及說(shuō)明

    React中關(guān)于render()的用法及說(shuō)明

    這篇文章主要介紹了React中關(guān)于render()的用法及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • React中使用Vditor自定義圖片詳解

    React中使用Vditor自定義圖片詳解

    這篇文章主要介紹了React中使用Vditor自定義圖片詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-12-12
  • React 三大屬性之state的使用詳解

    React 三大屬性之state的使用詳解

    這篇文章主要介紹了React 三大屬性之state的使用詳解,幫助大家更好的理解和學(xué)習(xí)使用React,感興趣的朋友可以了解下
    2021-04-04
  • React各種狀態(tài)管理器的解讀及使用方法

    React各種狀態(tài)管理器的解讀及使用方法

    這篇文章主要介紹了對(duì)于React各種狀態(tài)管理器的解讀,文中給大家提到了狀態(tài)管理器是如何使用的,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-12-12

最新評(píng)論