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) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      return;
    }
  }
}

function peek(heap) {
  return heap.length === 0 ? null : heap[0];
}

function pop(heap) {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  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];
    if (compare(left, node) < 0) {
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      return;
    }
  }
}

function compare(a, b) {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

这是 React 调度系统中的最小二叉堆实现，用于管理任务的优先级调度。让我详细解释每个函数：

一、整体结构

这是一个最小堆（Min Heap）数据结构，用于维护任务优先级队列，堆顶始终是优先级最高（数值最小）的任务。

二、详细分析

1. push(heap, node) - 插入节点

function push(heap, node) {
  const index = heap.length;  // 新节点的索引位置
  heap.push(node);            // 将节点添加到数组末尾
  siftUp(heap, node, index);  // 上浮调整堆结构
}

功能：将新节点插入堆中，然后通过上浮操作维护堆的性质。

示例：

const heap = [];
push(heap, { sortIndex: 3, id: 1 });  // 插入第一个元素
push(heap, { sortIndex: 1, id: 2 });  // 插入第二个元素，会上浮到堆顶
console.log(peek(heap));  // { sortIndex: 1, id: 2 }

2. siftUp(heap, node, i) - 上浮操作

function siftUp(heap, node, i) {
  let index = i;
  while (index > 0) {  // 当不是根节点时循环
    const parentIndex = (index - 1) >>> 1;  // 计算父节点索引
    const parent = heap[parentIndex];       // 获取父节点
    
    // 如果父节点比当前节点大（优先级低），交换位置
    if (compare(parent, node) > 0) {
      heap[parentIndex] = node;  // 将当前节点放到父节点位置
      heap[index] = parent;      // 将父节点放到当前节点位置
      index = parentIndex;       // 更新当前节点索引
    } else {
      return;  // 堆性质已满足，退出
    }
  }
}

关键操作：(index - 1) >>> 1

• >>> 是无符号右移运算符
• 对于正整数，(index - 1) >>> 1 等价于 Math.floor((index - 1) / 2)
• 这是计算二叉堆中父节点索引的标准方法

上浮过程：

初始堆: [3, 7, 5, 9, 8]
插入节点2: [3, 7, 5, 9, 8, 2]
第一步: 节点2(索引5)与父节点7(索引2)比较，2<7，交换
        [3, 2, 5, 9, 8, 7]
第二步: 节点2(索引2)与父节点3(索引0)比较，2<3，交换
        [2, 3, 5, 9, 8, 7] ← 堆性质恢复

3. peek(heap) - 查看堆顶

function peek(heap) {
  return heap.length === 0 ? null : heap[0];
}

功能：返回堆顶元素（最小值）但不移除。

时间复杂度：O(1)

4. pop(heap) - 弹出堆顶

function pop(heap) {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];  // 堆顶元素
  const last = heap.pop();  // 移除最后一个元素
  
  if (last !== first) {  // 如果堆中还有元素
    heap[0] = last;      // 将最后一个元素放到堆顶
    siftDown(heap, last, 0);  // 下沉调整
  }
  return first;  // 返回堆顶元素
}

工作流程：

1. 保存堆顶元素
2. 移除最后一个元素
3. 将最后一个元素放到堆顶
4. 执行下沉操作恢复堆性质

5. siftDown(heap, node, i) - 下沉操作

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];        // 右子节点
    
    // 如果左子节点比当前节点小
    if (compare(left, node) < 0) {
      // 如果存在右子节点且右子节点更小
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;       // 当前节点与右子节点交换
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;        // 当前节点与左子节点交换
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } 
    // 如果右子节点比当前节点小
    else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;         // 当前节点与右子节点交换
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      return;  // 堆性质已满足
    }
  }
}

关键点：

• halfLength = length >>> 1：只需要处理前一半的节点（非叶子节点）
• 左子节点索引：(index + 1) * 2 - 1 等价于 index * 2 + 1
• 总是与较小的子节点交换，保持最小堆性质

下沉过程：

初始堆: [9, 3, 5, 7, 8]  // 9是根节点，但9>3，违反最小堆性质
移除堆顶9，将8放到堆顶: [8, 3, 5, 7]
比较8和子节点3、5，3更小，交换8和3: [3, 8, 5, 7]
比较8和子节点7，7<8，交换8和7: [3, 7, 5, 8] ← 堆性质恢复

6. compare(a, b) - 比较函数

function compare(a, b) {
  const diff = a.sortIndex - b.sortIndex;  // 主要按sortIndex比较
  return diff !== 0 ? diff : a.id - b.id;  // sortIndex相同时按id比较
}

比较规则：

1. 优先比较 sortIndex（任务优先级）
2. 如果 sortIndex 相同，比较 id 保证稳定排序
3. 返回负数表示 a < b，零表示相等，正数表示 a > b

在 React 调度器中的应用：

• sortIndex：通常是过期时间（expiration time）或优先级
• id：任务创建时的自增ID，用于 FIFO（先进先出）

三、时间复杂度分析

操作	时间复杂度	说明
push()	O(log n)	插入节点并上浮调整
pop()	O(log n)	弹出堆顶并下沉调整
peek()	O(1)	查看堆顶
siftUp()	O(log n)	上浮操作，最坏情况到根节点
siftDown()	O(log n)	下沉操作，最坏情况到叶子节点

四、在 React 中的应用

1. 调度器任务队列

// React 调度器使用最小堆管理任务
const taskQueue = [];  // 任务堆

// 调度任务
function unstable_scheduleCallback(priorityLevel, callback) {
  const expirationTime = startTime + timeout;
  const newTask = {
    id: taskIdCounter++,
    callback,
    priorityLevel,
    startTime,
    expirationTime,
    sortIndex: expirationTime,  // 用过期时间作为排序依据
  };
  
  push(taskQueue, newTask);
  
  // 请求调度
  if (!isHostCallbackScheduled && !isPerformingWork) {
    isHostCallbackScheduled = true;
    requestHostCallback(flushWork);
  }
}

2. 工作循环

function flushWork(hasTimeRemaining, initialTime) {
  // 从堆中取出最高优先级任务
  let currentTask = peek(taskQueue);
  
  while (currentTask !== null) {
    if (currentTask.expirationTime > currentTime) {
      // 任务尚未过期，可以暂停
      break;
    }
    
    // 执行任务
    const callback = currentTask.callback;
    if (callback !== null) {
      currentTask.callback = null;
      callback();
    }
    
    // 弹出已完成任务
    pop(taskQueue);
    
    // 获取下一个任务
    currentTask = peek(taskQueue);
  }
}

五、关键特点

1. 最小堆性质：父节点的值总是小于等于子节点
2. 数组实现：使用数组存储完全二叉树
3. 高效操作：插入和删除都是 O(log n)
4. 稳定排序：当优先级相同时，按插入顺序（id）排序
5. 内存友好：数组存储比链表更节省内存

这个最小堆实现是 React 调度器的核心数据结构，确保了高优先级任务能够被及时处理，是 React 实现并发渲染和时间切片的基础。