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

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

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

1. 什么是最小堆

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

完全二叉樹的特點是：

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

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

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

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

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

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

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

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

export type Node = {
  id: number;        // 每個任務(wù)的唯一標識
  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ù)組末尾
從下往上進行堆化（siftUp），不斷與父節(jié)點比較，若比父節(jié)點小就交換，一直向上，直到滿足堆性質(zhì)
恢復最小堆性質(zhì)

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

// 插入元素
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) {
    // 無符號右移，相當于 /2 并且向下取整
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    // 如果父節(jié)點大于node，需要交換
    if (compare(parent, node) > 0) {
      // node子節(jié)點更小，和根節(jié)點交換
      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 刪除堆頂元素

刪除流程

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

// 刪除堆頂元素  先取出堆頂元素，然后取出最后一個元素放到堆頂，然后從上往下堆化
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個或者更多個元素
    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é)點，因為每次都是跟左半邊 或者 右半邊的節(jié)點對比
  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à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 最小堆實現(xiàn)小結(jié)的文章就介紹到這了,更多相關(guān)React Scheduler 最小堆內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: