前端任务怎样按优先级排队？二叉堆为什么不需要每次完整排序？

简答

二叉堆是用数组表示的完全二叉树，堆顶是优先级最高的元素。
插入时向上调整，取出时把最后一个元素移到堆顶再向下调整，都是 O(log n)。
不需要每次都完整排序，查看堆顶是 O(1)。
堆本身不稳定，同优先级需要先进先出时，可以额外记录递增序号作为次级比较键。

图片预加载队列同时收到“当前视口图片”和“下一页图片”。FIFO 只看进入顺序，可能让用户正需要的任务排在许多预取任务后面；每插入一次就重新排序整个数组又会做很多重复工作。优先队列希望随时取出当前最重要的一项，二叉堆是常见实现。

这里规定数值越小越优先，同优先级按提交顺序取出。优先级只决定等待任务的选择，不会抢占已经执行的 JavaScript 或自动取消网络请求。

堆只保持局部次序

最小堆要求每个父节点不大于它的孩子，根节点因此是全局最小值；兄弟节点之间不要求排序。数组索引 i 的孩子位于 2i+1 与 2i+2，父节点位于 floor((i-1)/2)。

插入先放到数组末尾，与父节点比较并向上交换；取出根节点后，用末尾节点补到根部，再与更小的孩子交换直到恢复约束。每次只沿树高移动，不需要重新整理所有节点。

JavaScript

class PriorityQueue {
  #heap = [];
  #sequence = 0;

  get size() { return this.#heap.length; }

  #before(a, b) {
    return a.priority < b.priority ||
      (a.priority === b.priority && a.sequence < b.sequence);
  }

  push(value, priority) {
    if (!Number.isFinite(priority)) throw new TypeError('优先级必须为有限数值');
    if (!Number.isSafeInteger(this.#sequence)) throw new RangeError('序号已超出安全范围');
    const item = { value, priority, sequence: this.#sequence++ };
    const heap = this.#heap;
    heap.push(item);
    let index = heap.length - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (!this.#before(heap[index], heap[parent])) break;
      [heap[index], heap[parent]] = [heap[parent], heap[index]];
      index = parent;
    }
  }

  pop() {
    const heap = this.#heap;
    if (heap.length === 0) return undefined;
    const first = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let index = 0;
      while (true) {
        const left = index * 2 + 1;
        if (left >= heap.length) break;
        const right = left + 1;
        let smaller = left;
        if (right < heap.length && this.#before(heap[right], heap[left])) smaller = right;
        if (!this.#before(heap[smaller], heap[index])) break;
        [heap[index], heap[smaller]] = [heap[smaller], heap[index]];
        index = smaller;
      }
    }
    return { value: first.value, priority: first.priority };
  }
}

const queue = new PriorityQueue();
queue.push('下一页图片', 5);
queue.push('视口图片 A', 1);
queue.push('视口图片 B', 1);
console.log(queue.pop().value); // 视口图片 A
console.log(queue.pop().value); // 视口图片 B
console.log(queue.pop().value); // 下一页图片
console.log(queue.pop()); // undefined

pop 返回包装对象，所以即使 value 本身是 undefined，也能与空队列返回 undefined 区分。sequence 是独立的插入序号：只比较 priority 的堆不保证同优先级稳定顺序。

为什么下沉要选更小的孩子

根被较大的末尾值替换后，必须让两个孩子中更小的那个上来。若随便选左孩子，而右孩子更小，交换后的父节点仍会违反堆序。边界还包括只有左孩子、队列原来只有一个元素以及空队列；示例逐一处理，而不是假定节点总有两个孩子。

在常见数组访问模型下，push 和 pop 沿树高移动，时间 O(log n)，读取 size 是 O(1)，保存 n 个节点需要 O(n) 空间。若一次性装入大量初始数据，自底向上的建堆可以做到 O(n)，不必反复 push；本例没有实现该批量入口。

优先级变化不能直接改节点字段

任务从预取变成可见资源时，可能需要提高优先级。本例不暴露内部节点，避免外部直接改 priority 后破坏堆序。若要支持修改，可以维护任务 ID 到索引的映射，每次交换同步更新，再决定上浮或下沉；另一种方案是插入新版本，弹出时丢弃过期版本，但要控制旧条目堆积。

取消等待任务也需要额外协议。惰性取消可把任务 ID 标记失效，pop 时跳过；大量失效条目需定期整理，不能无限增长。已经运行的 fetch 或 Worker 则通过其自己的取消机制处理，删除堆节点不能撤销已发生的副作用。

与并发池组合时要避免饥饿

优先队列只选择下一个任务，执行器另行限制并发数。不要把所有 pop 出来的任务立即 Promise.all，否则优先级只影响启动的瞬间，后续仍会全部占用资源。

高优先级任务源源不断时，低优先级任务可能长期得不到执行。可以按业务设置等待时间提升、不同队列配额或最大延迟。时间老化若影响比较规则，不能让比较器悄悄依赖 Date.now 后期待旧堆自动重新有序，应明确重建或更新策略。

用户可控制优先级时要限制取值与权限，不允许普通任务无限宣称最高优先级。队列还需限制数量、载荷和等待时间，避免内存耗尽。小规模列表直接排序可能更容易维护；频繁插入并取最小任务时，堆才更有价值。

本题为教学实现，不是完整浏览器调度器。浏览器资源优先级、事件循环任务优先级与应用的这个数值队列是不同层次，不能相互等同。