結(jié)合 React 源碼，五分鐘帶你掌握優(yōu)先隊列

什么是優(yōu)先隊列

優(yōu)先隊列是數(shù)據(jù)結(jié)構(gòu)中的基礎(chǔ)概念，與隊列先進先出（FIFO）的出隊順序不同的是 ，它的出隊順序與元素的優(yōu)先級相關(guān)。

例如 React 的時間分片（React Fiber），它將渲染任務(wù)分了優(yōu)先級，出隊的順序與任務(wù)的“重要程度”存在關(guān)系，那么滿足這種情況的數(shù)據(jù)結(jié)構(gòu)就是 優(yōu)先隊列 。

優(yōu)先隊列的操作

• 插入：在優(yōu)先隊列中插入元素，并使隊列“有序”
• 刪除最大/最小值：刪除并返回最大/最小的元素，并使隊列“有序”
• 查找最大/最小關(guān)鍵字：查找最大/最小的值

優(yōu)先隊列的實現(xiàn)比較

二叉堆

在二叉堆中數(shù)組中，要保證每個元素都小于（大于）或等于另外兩個特定位置的元素。例如下圖的樹中，父節(jié)點總是小于或等于子節(jié)點。

對于二叉堆有如下性質(zhì)：

• 節(jié)點 k 的父節(jié)點下標(biāo)為 k / 2（向下取整）
• 以某節(jié)點為根節(jié)點的子樹，該節(jié)點是這顆樹的極值

二叉堆的操作

插入

二叉堆的插入非常簡單，只需要在二叉堆的最后添加要插入的內(nèi)容，并將其“上浮”到正確位置。

嘗試在上面的二叉堆中插入新元素 9，過程如下：

在尾部插入元素 9，與父節(jié)點進行對比，有序性被破壞，與父元素替換位置。

替換成功后，繼續(xù)上一輪操作，與父節(jié)點進行對比，仍然無法滿足有序性，繼續(xù)調(diào)換位置。

再次替換后符合。

程序框架

function?push?{
??*?在堆尾部添加元素
??*?執(zhí)行上浮循環(huán)
????*?與父元素對比大小，將較大的放在父節(jié)點位置
??
??return?minItem
}

實現(xiàn)

function?push(heap:?Heap,?node:?Node):?void?{
??const?index?=?heap.length;
??heap.push(node);?//?在堆尾部添加元素
??siftUp(heap,?node,?index);?//?進行上浮操作
}

function?siftUp(heap,?node,?i)?{
??let?index?=?i;
??while?(true)?{
????const?parentIndex?=?(index?-?1)?>>>?1;?//?父節(jié)點位置：parentIndex = childIndex / 2
????const?parent?=?heap[parentIndex];
????if?(parent?!==?undefined?&&?compare(parent,?node)?>?0)?{
??????//?The?parent?is?larger.?Swap?positions.
??????heap[parentIndex]?=?node;
??????heap[index]?=?parent;
??????index?=?parentIndex;
????}?else?{
??????//?The?parent?is?smaller.?Exit.
??????return;
????}
??}
}

刪除

取出根節(jié)點的值對比插入稍微復(fù)雜一點，歸納起來可以分為三步：

1. 取出根節(jié)點的值
2. 將最后一個元素與根節(jié)點進行替換，并刪除最后一個元素
3. 下沉

取出根節(jié)點。

將最后一個元素與根節(jié)點調(diào)換，并刪除。對比發(fā)現(xiàn)有序性被破壞，進行對調(diào)。

完成刪除。

程序框架

function?pop?{
??*?設(shè)定?minItem?保存根節(jié)點
??*?取出最后一個節(jié)點與根節(jié)點替換，并刪除最后一個節(jié)點
??*?執(zhí)行下沉循環(huán)
????*?將根元素與左右子節(jié)點對比,挑選較小的與父節(jié)點替換位置
??
??return?minItem
}

實現(xiàn)

export?function?pop(heap:?Heap):?Node?|?null?{
??const?first?=?heap[0];?//?取出根節(jié)點
??if?(first?!==?undefined)?{
????const?last?=?heap.pop();?//?取出最后一位元素，并刪除
????if?(last?!==?first)?{
??????heap[0]?=?last;?//?與根節(jié)點對調(diào)
??????siftDown(heap,?last,?0);?//?下沉
????}
????return?first;
??}?else?{
????return?null;
??}
}

function?siftDown(heap,?node,?i)?{
??let?index?=?i;
??const?length?=?heap.length;
??while?(index?????const?leftIndex?=?(index?+?1)?*?2?-?1;
????const?left?=?heap[leftIndex];
????const?rightIndex?=?leftIndex?+?1;
????const?right?=?heap[rightIndex];

????//?If?the?left?or?right?node?is?smaller,?swap?with?the?smaller?of?those.
????//?尋找左右兒子較小的那一個替換
????if?(left?!==?undefined?&&?compare(left,?node)?0)?{?//左子節(jié)點小于根節(jié)點
??????if?(right?!==?undefined?&&?compare(right,?left)?0)?{
????????heap[index]?=?right;
????????heap[rightIndex]?=?node;
????????index?=?rightIndex;
??????}?else?{
????????heap[index]?=?left;
????????heap[leftIndex]?=?node;
????????index?=?leftIndex;
??????}
????}?else?if?(right?!==?undefined?&&?compare(right,?node)?0)?{?//?左子節(jié)點大于根節(jié)點，右子節(jié)點小于根節(jié)點
??????heap[index]?=?right;
??????heap[rightIndex]?=?node;
??????index?=?rightIndex;
????}?else?{
??????//?Neither?child?is?smaller.?Exit.
??????return;
????}
??}
}

以下是 React 源碼中 scheduler/src/SchedulerMinHeap.js 關(guān)于最小堆的完整實現(xiàn)：

/**
?*?Copyright?(c)?Facebook,?Inc.?and?its?affiliates.
?*
?*?This?source?code?is?licensed?under?the?MIT?license?found?in?the
?*?LICENSE?file?in?the?root?directory?of?this?source?tree.
?*
?*?@flow?strict
?*/

//?定義最小堆極其元素，其中?sortIndex?為最小堆對比的?key，若?sortIndex?相同，則對比?id
type?Heap?=?Array;
type?Node?=?{|
??id:?number,
??sortIndex:?number,
|};

//?入隊操作，在入隊完成之后進行“上浮”
export?function?push(heap:?Heap,?node:?Node):?void?{
??const?index?=?heap.length;
??heap.push(node);
??siftUp(heap,?node,?index);
}

//?查找最大值
export?function?peek(heap:?Heap):?Node?|?null?{
??const?first?=?heap[0];
??return?first?===?undefined???null?:?first;
}

//?刪除并返回最大值
export?function?pop(heap:?Heap):?Node?|?null?{
??const?first?=?heap[0];?//?取出根節(jié)點（哨兵）
??if?(first?!==?undefined)?{
????const?last?=?heap.pop();?//?取出最后一位元素，并刪除
????if?(last?!==?first)?{?//?頭尾并沒有對撞
??????heap[0]?=?last;?//?與根節(jié)點對調(diào)
??????siftDown(heap,?last,?0);?//?下沉
????}
????return?first;
??}?else?{
????return?null;
??}
}

//?上浮，調(diào)整樹結(jié)構(gòu)
function?siftUp(heap,?node,?i)?{
??let?index?=?i;
??while?(true)?{
????const?parentIndex?=?(index?-?1)?>>>?1;?//?父節(jié)點位置：parentIndex = childIndex / 2，此處使用位操作，右移一位
????const?parent?=?heap[parentIndex];
????if?(parent?!==?undefined?&&?compare(parent,?node)?>?0)?{?//?對比父節(jié)點和子元素的大小
??????//?The?parent?is?larger.?Swap?positions.
??????heap[parentIndex]?=?node;?//?若父節(jié)點較大，則更換位置
??????heap[index]?=?parent;
??????index?=?parentIndex;
????}?else?{
??????//?The?parent?is?smaller.?Exit.
??????return;
????}
??}
}

//?下沉，調(diào)整樹結(jié)構(gòu)
function?siftDown(heap,?node,?i)?{
??let?index?=?i;
??const?length?=?heap.length;
??while?(index?????const?leftIndex?=?(index?+?1)?*?2?-?1;
????const?left?=?heap[leftIndex];
????const?rightIndex?=?leftIndex?+?1;
????const?right?=?heap[rightIndex];

????//?If?the?left?or?right?node?is?smaller,?swap?with?the?smaller?of?those.
????//?尋找左右兒子較小的那一個替換
????if?(left?!==?undefined?&&?compare(left,?node)?0)?{
??????if?(right?!==?undefined?&&?compare(right,?left)?0)?{?//?左子節(jié)點小于根節(jié)點
????????heap[index]?=?right;
????????heap[rightIndex]?=?node;
????????index?=?rightIndex;
??????}?else?{
????????heap[index]?=?left;
????????heap[leftIndex]?=?node;
????????index?=?leftIndex;
??????}
????}?else?if?(right?!==?undefined?&&?compare(right,?node)?0)?{?//?左子節(jié)點大于根節(jié)點，右子節(jié)點小于根節(jié)點
??????heap[index]?=?right;
??????heap[rightIndex]?=?node;
??????index?=?rightIndex;
????}?else?{
??????//?Neither?child?is?smaller.?Exit.
??????return;
????}
??}
}

function?compare(a,?b)?{
??//?Compare?sort?index?first,?then?task?id.
??const?diff?=?a.sortIndex?-?b.sortIndex;
??return?diff?!==?0???diff?:?a.id?-?b.id;
}

堆排序

利用最大/最小堆的特性，我們很容易就能實現(xiàn)對數(shù)組的排序，重復(fù)執(zhí)行 pop 就能進行升序排列，如果要降序，使用最大堆即可，該操作時間復(fù)雜度為 nlogn。

多叉堆

為了追求更優(yōu)的時間復(fù)雜度，我們可以將二叉堆改為多叉堆實現(xiàn)，下圖為一個三叉堆：

與二叉堆不同的是對于含有 N 個元素的 d 叉堆（通常情況下 d >= 2），隨著 d 的增加，樹高 K = logdN 的斜率會下降，然而 d 越大，刪除操作的成本會更高。所以子元素不是越多越好，通常情況下三叉堆和四叉堆的應(yīng)用會比較常見。

在 libev 中有這么一段注釋 https://github.com/enki/libev/blob/master/ev.c#L2227，他提及了四叉樹相比二叉堆來說緩存更加友好。根據(jù) benchmark，在 50000+ 個 watchers 的場景下，四叉樹會有 5% 的性能優(yōu)勢。

/*
?*?at?the?moment?we?allow?libev?the?luxury?of?two?heaps,
?*?a?small-code-size?2-heap?one?and?a?~1.5kb?larger?4-heap
?*?which?is?more?cache-efficient.
?*?the?difference?is?about?5%?with?50000+?watchers.
?*/

同樣 Go 語言中的定時器的 timersBucket 的數(shù)據(jù)結(jié)構(gòu)也采用了最小四叉堆。

結(jié)語

多叉堆，例如四叉堆更加適合數(shù)據(jù)量大，對緩存要求友好對場景。二叉堆適用數(shù)據(jù)量比較小且頻繁插入和刪除的場景。通常情況下二叉堆可以滿足大部分情況下的需求，如果編寫底層代碼，并且對性能有更高的要求，那么可以考慮多叉堆實現(xiàn)優(yōu)先隊列。

最后

• 歡迎加我微信(winty230)，拉你進技術(shù)群，長期交流學(xué)習(xí)...
  

• 歡迎關(guān)注「前端Q」,認(rèn)真學(xué)前端，做個專業(yè)的技術(shù)人...

點個在看支持我吧