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;
    }
  }
}