快捷導(dǎo)航

React Scheduler 最小堆實(shí)現(xiàn)小結(jié)

更新時(shí)間：2026年01月27日 09:45:25 作者：_DoubleL

本文主要介紹了React Scheduler 最小堆實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

1. 什么是最小堆

最小堆（Min Heap）是一種完全二叉樹結(jié)構(gòu)，同時(shí)滿足一個(gè)很關(guān)鍵的性質(zhì)：任意一個(gè)節(jié)點(diǎn)的值，都 ≤ 它的左右子節(jié)點(diǎn)的值，也就是說： ?? 堆頂（根節(jié)點(diǎn)）一定是整個(gè)結(jié)構(gòu)中最小的元素

完全二叉樹的特點(diǎn)是：

從上到下
從左到右依次填滿
只允許最后一層不滿

2. 用數(shù)組表示最小堆??

最小堆通常用數(shù)組實(shí)現(xiàn)，而不是鏈表。

索引: 0 1 2 3 4 5
數(shù)組: [1, 3, 5, 4, 6, 8]

如果數(shù)組下標(biāo)從 0 開始：

父節(jié)點(diǎn)：(i - 1) >>> 1;
左子節(jié)點(diǎn)：2 * i + 1
右子節(jié)點(diǎn)：2 * i + 2

3. React Scheduler 最小堆實(shí)現(xiàn)

React 的 Scheduler 內(nèi)部，正是通過 最小堆 + sortIndex 來維護(hù)任務(wù)執(zhí)行順序

export type Node = {
  id: number;        // 每個(gè)任務(wù)的唯一標(biāo)識(shí)
  sortIndex: number; // 決定任務(wù)順序
};

堆的本質(zhì)：數(shù)組

export type Heap<T extends Node> = Array<T>;

3.1 取出堆頂元素

export const peek = <T extends Node>(heap: Heap<T>): T | null => {
  return heap.length === 0 ? null : heap[0];
};

3.2 插入元素

插入流程：

新元素放到數(shù)組末尾
從下往上進(jìn)行堆化（siftUp），不斷與父節(jié)點(diǎn)比較，若比父節(jié)點(diǎn)小就交換，一直向上，直到滿足堆性質(zhì)
恢復(fù)最小堆性質(zhì)

如下圖，在最后的節(jié)點(diǎn)插入1， 1和父節(jié)點(diǎn)（10）交換位置，接著 1和父節(jié)點(diǎn)（2）交換位置，就變成了恢復(fù)了最小堆

// 插入元素
export const push = <T extends Node>(heap: Heap<T>, node: T): void => {
  // 1. 把node放到堆的最后
  const index = heap.length;
  heap.push(node);
  // 2. 調(diào)整最小堆，從下往上堆化
  siftUp(heap, node, index);
};
?
// 從下往上堆化
export const siftUp = <T extends Node>(
  heap: Heap<T>,
  node: T,
  i: number,
): void => {
  let index = i;
?
  while (index > 0) {
    // 無符號(hào)右移，相當(dāng)于 /2 并且向下取整
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    // 如果父節(jié)點(diǎn)大于node，需要交換
    if (compare(parent, node) > 0) {
      // node子節(jié)點(diǎn)更小，和根節(jié)點(diǎn)交換
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      return;
    }
  }
};
?
// 比較函數(shù)，返回值大于0 表示 a大于b
function compare(a: Node, b: Node) {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

3.3 刪除堆頂元素

刪除流程

保存堆頂元素（最小值）
取出最后一個(gè)元素
放到堆頂
從上往下堆化（siftDown），比較 node 與左右子節(jié)點(diǎn)，選擇更小的那個(gè)子節(jié)點(diǎn)，若子節(jié)點(diǎn)更小，則交換，一路向下，直到恢復(fù)堆序

// 刪除堆頂元素  先取出堆頂元素，然后取出最后一個(gè)元素放到堆頂，然后從上往下堆化
export const pop = <T extends Node>(heap: Heap<T>): T | null => {
  if (!heap.length) return null;
  const first = heap[0];
  const last = heap.pop()!;
  if (first !== last) {
    // 證明heap中有2個(gè)或者更多個(gè)元素
    heap[0] = last;
    siftDown(heap, last, 0);
  }
  return first;
};

// 從上往下堆化
function siftDown<T extends Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  const length = heap.length;
  // 只需要取一半的節(jié)點(diǎn)，因?yàn)槊看味际歉蟀脒?或者 右半邊的節(jié)點(diǎn)對(duì)比
  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]; // right不一定存在，等下還要判斷是否存在
    if (compare(left, node) < 0) {
      // left<node
      if (rightIndex < length && compare(right, left) < 0) {
        // right存在，且right<left
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        // left更小或者right不存在
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < length && compare(right, node) < 0) {
      // left>=node && right<node
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // 根節(jié)點(diǎn)最小，不需要調(diào)整
      return;
    }
  }
}

// 比較函數(shù)，返回值大于0 表示 a大于b
function compare(a: Node, b: Node) {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

到此這篇關(guān)于React Scheduler 最小堆實(shí)現(xiàn)小結(jié)的文章就介紹到這了,更多相關(guān)React Scheduler 最小堆內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: