跳到主要内容

SchedulerMinHeap （调度器的最小堆）

调度器的最小堆 。

信息
  • 最小堆 ： 父节点 ≤ 子节点 （根是最小值）
  • 最大堆 ： 父节点 ≥ 子节点 （根是最大值）

一、 添加 node​

export function push<T extends Node>(heap: Heap<T>, node: T): void {
  const index = heap.length;
  heap.push(node); // 先放到最后
  siftUp(heap, node, index); // 再“上浮”到正确位置
}

二、 查看堆顶​

根据当前的堆的长度，返回推顶，没有则返回 null。

仅进行堆顶的查看，不移除堆顶。

export function peek<T extends Node>(heap: Heap<T>): T | null {
  // 根据堆长度返回堆顶或 `null`
  return heap.length === 0 ? null : heap[0];
}

三、弹出​

弹出堆顶，如果堆为空，则返回 null

export function pop<T extends Node>(heap: Heap<T>): T | null {
  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. 比较函数​

比较函数
function compare(a: Node, b: Node) {
  // 优先比较短下标，如果相同再比较任务 ID
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;

  return diff !== 0 ? diff : a.id - b.id;
}

2. 上浮​

新元素插在末尾，可能比父节点小，破坏了“最小堆”性质。

所以要不断和父节点比较，如果更小，就交换，知道合适位置。

function shiftUp<T extends Node>(heap: Heap<T>, node: T, i: number): void {
  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 {
      // 父对象更小，直接退出
      //  The parent is smaller. Exit.
      return;
    }
  }
}

3. 下沉​

把最后一个元素放到根后，他可能比孩子大，破坏堆性质。

所以要不断和更小的那个孩子比较，如果更大，就交换，知道合适的位置。

function siftDown<T extends Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  // 堆的长度
  const length = heap.length;
  // 堆一半的长度（保证了半堆永远有效的）
  // 所有非叶子节点的范围是 [0, half)
  const halfLength = length >>> 1;

  // 通过两两比较
  while (index < halfLength) {
    // 也可以写成  = (index << 1) + 1;
    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 (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 {
      // 两个孩子都不小，退出
      // Neither child is smaller. Exit.
      return;
    }
  }
}

五、补充（二叉堆）​

堆（ Heap ） 是一个能 快速拿到最大/最小值 、并 高效插入新元素 的数据结构。首先出现在 1964 年 J.W.J.Williams 在论文 “Algorithm 232: Heapsort“ 中，作为 **堆排序（Heapsort）算法的一部分。是用于早期 **伪代码或汇编/早期 Fortran** 描述。

1. 二叉堆​

堆是一颗 完全二叉树 ， 但不用真的建树，而是用 数组 储存。

  • 完全二叉树 ： 用数组紧凑储存，无空洞
  • 堆性质 ：
    • 最小堆： 父节点 ≤ 子节点 （根是最小值）
    • 最大堆： 父节点 ≥ 子节点 （根是最大值）

2. 实现（最小堆）​

class MinHeap<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;

  constructor(compareFn?: (a: T, b: T) => number) {
    // 默认为数字最小堆
    this.compare = compareFn ?? ((a, b) => (a as any) - (b as any));
  }
  // 二叉堆的长度
  size(): number {
    return this.heap.length;
  }
  // 二叉堆是否为空
  isEmpty(): boolean {
    return this.size() === 0;
  }
  // 查看最小值，但不移除
  // 时间复杂度：O(1) （直接取数组第一个元素）
  peek(): T | undefined {
    return this.heap[0];
  }

  push(value: T): void {
    this.heap.push(value); // 先放到最后
    this.siftUp(this.heap.length - 1); // 再“上浮”到正确位置
  }
  // 去除最小值
  pop(): T | undefined {
    if (this.isEmpty()) return undefined;
    // 保存最小值
    const top = this.heap[0];
    // 取出最后一个元素
    const last = this.heap.pop();

    if (!this.isEmpty()) {
      // 把最后一个元素放到根
      this.heap[0] = last;
      // “下沉”调整
      this.siftDown(0);
    }
    return top;
  }
  // 新元素插到末尾，可能比父节点小，破坏了“最小堆”性质
  // 所以要不断的跟父节点进行比较，如果更小，就交换，知道合适位置
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.compare(this.heap[i], this.heap[parent]) >= 0) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
  // 下沉
  private siftDown(i: number): void {
    const n = this.heap.length;
    // 非叶子节点范围 [0, half)
    const half = n >>> 1;

    while (i < half) {
      let child = (i << 1) + 1; // 左子节点
      const right = child + 1;
      // 选择更小的子节点
      // 如果右孩子存在，且，比左孩子更小，选右孩子
      if (right < n && this.compare(this.heap[right], this.heap[child]) < 0) {
        child = right;
      }

      // 如果当前节点 ≤ 最小孩子，停止
      if (this.compare(this.heap[i], this.heap[child]) <= 0) break;

      // 否则交换
      [this.heap[i], this.heap[child]] = [this.heap[child], this.heap[i]];

      i = child; // 继续向下查找
    }
  }
}

3. 使用​

数字最小堆
const heap = new MinHeap<number>();

heap.push(5);
heap.push(3);
heap.push(9);
heap.push(1);
heap.push(6);
// [1, 3, 9, 5, 6]
console.log(heap.heap);

4. 使用场景​

场景说明
堆排序原地排序，时间复杂度 O(n ㏒ n )
优先队列任务调度、事件处理
Top-K 问题找到最大的 K 个元素（用最小堆维护 K 个）
Dijkstra 算法用堆优化最小距离节点
合并 K 个有序列表每次取堆顶最小元素

5. 注意事项​

  • 不要直接修改 heap 数组 ， 否则会破坏堆结构
  • 比较函数必须满足全序关系 ， 即对任意 a ， b ， c ：可比、反对称、传递
  • 性能 ：插入/删除均为 O(㏒ n) ，空间 O(n)

6. 语言支持​

语言是否内置/优先列队说明
C++✅ 是std:priority_queue 底层通常是二叉堆
Java✅ 是java.util.PriorityQueue 基于二叉堆
Python✅ 是heapq 模块，提供最小堆操作函数
C#✅ .NET 6+PriorityQueue<T, TPriority>
Go❌ 否需手动实现或用第三方库（如 container/heap
JavaScript❌ 否标注库没有堆，需要自己实现或用 npm 包
Rust✅ 标准库std::collections::BinaryHeap 最大堆

7. 堆排序和快排​

堆本身就是为了排序而生的。

  • 时间复杂度 ： O(n ㏒ n)
  • 空间复杂度 ： O(1) 原地排序
  • 稳定性 ： 不稳定
  • 原理 ：
    • 将数组 原地构建成最大堆 （ O(n) ）
    • 重复执行：
      • 把堆顶（最大值）和末尾元素交换
      • 缩小堆范围，排除已排好的末尾
      • 堆新堆顶执行 siftDown
    • 最终数组生序排列
快速排序堆排序归并排序
平均时间O(n ㏒ n)O(n ㏒ n)O(n ㏒ n)
最坏时间O(n²)O(n ㏒ n)O(n ㏒ n)
空间O(n ㏒ n)O(1)O(n)
实际速度⚡️ 很快🐢 很慢快
稳定性❌ 否❌ 否✅ 是