Untitled

作者：oasis

用具体例子说明最小堆的工作过程：

示例：任务调度最小堆

假设有以下任务需要调度：

// 任务格式：{ id: number, sortIndex: number }
// sortIndex 越小，优先级越高

任务1: { id: 1, sortIndex: 5 }  // 优先级 5
任务2: { id: 2, sortIndex: 3 }  // 优先级 3
任务3: { id: 3, sortIndex: 7 }  // 优先级 7
任务4: { id: 4, sortIndex: 1 }  // 优先级 1 (最高)
任务5: { id: 5, sortIndex: 4 }  // 优先级 4

步骤1：插入任务（push）

初始堆为空：heap = []

插入任务1 (sortIndex: 5)

heap = [任务1]
       [5]

堆只有一个元素，无需调整。

插入任务2 (sortIndex: 3)

插入后：heap = [任务1, 任务2]
                [5,    3]

siftUp 过程：
- 任务2 在索引1，父节点是索引0的任务1
- compare(任务1, 任务2) = 5 - 3 = 2 > 0，父节点更大
- 交换：heap = [任务2, 任务1]
                [3,    5]

结果：heap = [任务2(3), 任务1(5)]

插入任务3 (sortIndex: 7)

插入后：heap = [任务2, 任务1, 任务3]
                [3,    5,    7]

siftUp 过程：
- 任务3 在索引2，父节点是索引0的任务2
- compare(任务2, 任务3) = 3 - 7 = -4 < 0，父节点更小
- 无需交换，直接返回

结果：heap = [任务2(3), 任务1(5), 任务3(7)]

插入任务4 (sortIndex: 1) - 最高优先级

插入后：heap = [任务2, 任务1, 任务3, 任务4]
                [3,    5,    7,    1]

siftUp 过程（第1轮）：
- 任务4 在索引3，父节点是索引1的任务1
- compare(任务1, 任务4) = 5 - 1 = 4 > 0，父节点更大
- 交换：heap = [任务2, 任务4, 任务3, 任务1]
                [3,    1,    7,    5]

siftUp 过程（第2轮）：
- 任务4 现在在索引1，父节点是索引0的任务2
- compare(任务2, 任务4) = 3 - 1 = 2 > 0，父节点更大
- 交换：heap = [任务4, 任务2, 任务3, 任务1]
                [1,    3,    7,    5]

结果：heap = [任务4(1), 任务2(3), 任务3(7), 任务1(5)]

插入任务5 (sortIndex: 4)

插入后：heap = [任务4, 任务2, 任务3, 任务1, 任务5]
                [1,    3,    7,    5,    4]

siftUp 过程：
- 任务5 在索引4，父节点是索引1的任务2
- compare(任务2, 任务5) = 3 - 4 = -1 < 0，父节点更小
- 无需交换

最终堆：heap = [任务4(1), 任务2(3), 任务3(7), 任务1(5), 任务5(4)]

步骤2：查看堆顶（peek）

peek(heap) // 返回任务4 { id: 4, sortIndex: 1 }

返回优先级最高的任务，不删除。

步骤3：弹出堆顶（pop）

弹出任务4

初始：heap = [任务4, 任务2, 任务3, 任务1, 任务5]
             [1,    3,    7,    5,    4]

步骤1：保存根节点任务4
步骤2：用最后一个节点任务5替换根节点
       heap = [任务5, 任务2, 任务3, 任务1]
              [4,    3,    7,    5]

步骤3：siftDown 调整（第1轮）：
- 任务5 在索引0，左子节点是索引1的任务2，右子节点是索引2的任务3
- compare(任务2, 任务5) = 3 - 4 = -1 < 0，左子节点更小
- compare(任务3, 任务2) = 7 - 3 = 4 > 0，左子节点更小
- 与左子节点交换：heap = [任务2, 任务5, 任务3, 任务1]
                          [3,    4,    7,    5]

步骤4：siftDown 调整（第2轮）：
- 任务5 现在在索引1，左子节点是索引3的任务1
- compare(任务1, 任务5) = 5 - 4 = 1 > 0，子节点更大
- 无需交换，退出

结果：heap = [任务2(3), 任务5(4), 任务3(7), 任务1(5)]，返回任务4。

步骤4：继续弹出

弹出任务2

初始：heap = [任务2, 任务5, 任务3, 任务1]
             [3,    4,    7,    5]

用任务1替换根节点：
heap = [任务1, 任务5, 任务3]
       [5,    4,    7]

siftDown：
- compare(任务5, 任务1) = 4 - 5 = -1 < 0，左子节点更小
- 交换：heap = [任务5, 任务1, 任务3]
              [4,    5,    7]

结果：heap = [任务5(4), 任务1(5), 任务3(7)]，返回任务2。

完整操作序列总结

操作序列：
push(任务1) → [任务1(5)]
push(任务2) → [任务2(3), 任务1(5)]
push(任务3) → [任务2(3), 任务1(5), 任务3(7)]
push(任务4) → [任务4(1), 任务2(3), 任务3(7), 任务1(5)]
push(任务5) → [任务4(1), 任务2(3), 任务3(7), 任务1(5), 任务5(4)]

pop() → 返回任务4(1), 堆变为: [任务2(3), 任务5(4), 任务3(7), 任务1(5)]
pop() → 返回任务2(3), 堆变为: [任务5(4), 任务1(5), 任务3(7)]
pop() → 返回任务5(4), 堆变为: [任务1(5), 任务3(7)]
pop() → 返回任务1(5), 堆变为: [任务3(7)]
pop() → 返回任务3(7), 堆变为: []

关键点

最小堆保证根节点始终是最小值（最高优先级）
siftUp：插入时从下往上调整
siftDown：删除时从上往下调整
时间复杂度：push 和 pop 都是 O(log n)，peek 是 O(1)
比较规则：先比较 sortIndex，相同则比较 id

这样 React Scheduler 可以高效地按优先级调度任务。