React?之最小堆min?heap圖文詳解
二叉樹(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中的useMemo和useCallback的區(qū)別
React中的useMemo和useCallback是兩個(gè)重要的Hooks。常常被用于優(yōu)化組件的性能。雖然這兩個(gè)Hooks看起來(lái)很相似,但它們彼此之間還是有很大的區(qū)別的,隨著小編一起來(lái)學(xué)習(xí)吧2023-04-04React中使用react-json-view展示JSON數(shù)據(jù)的操作方法
react-json-view是一個(gè)用于顯示和編輯javascript數(shù)組和JSON對(duì)象的React組件,本文給大家分享React中使用react-json-view展示JSON數(shù)據(jù)的操作方法,感興趣的朋友一起看看吧2023-12-12react性能優(yōu)化達(dá)到最大化的方法 immutable.js使用的必要性
這篇文章主要為大家詳細(xì)介紹了react性能優(yōu)化達(dá)到最大化的方法,一步一步優(yōu)化react性能的過(guò)程,告訴大家使用immutable.js的必要性,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-03-03React中關(guān)于render()的用法及說(shuō)明
這篇文章主要介紹了React中關(guān)于render()的用法及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02