如何在JavaScript中实现带任务优先级的Promise队列？

问题描述 #

我想要在JavaScript中构建一个基于Promise的队列，要求：

• 每个任务返回一个Promise，队列需逐个处理任务，等待前一个Promise resolve后再启动下一个任务。
• 每个任务有优先级，高优先级任务需要插队：添加高优先级任务后，无论它在队列中的位置如何，都应该在当前运行的任务完成后作为下一个任务执行。

给出的基础代码结构：

class Task {
  constructor(fn, priority) {
    this.fn = fn;
    this.priority = priority;
  }
}

class PriorityPromiseQueue {
  // 需要实现
}

PriorityPromiseQueue需要按优先级顺序处理Task对象，调用每个Task.fn函数（该函数返回Promise）。

我考虑过使用数组并按优先级排序，但想知道是否有更高效的方式，尤其是在任务数量较多时。

实现方案 #

方案一：基于数组的简单实现（适合中小规模任务） #

这种实现思路是维护一个任务数组，每次准备处理下一个任务时，从队列中筛选出优先级最高的任务执行。代码简洁易懂，适合任务数量不多的场景。

核心逻辑：

• 用数组存储任务队列，标记isProcessing判断当前是否有任务在执行。
• 添加任务时，若当前无任务执行，直接启动处理流程；否则等待当前任务完成后自动处理。
• 每次处理任务时，遍历队列找出优先级最高的任务，执行完成后递归处理下一个。

代码实现：

class Task {
  constructor(fn, priority) {
    this.fn = fn;
    this.priority = priority;
  }
}

class PriorityPromiseQueue {
  constructor() {
    this.queue = [];
    this.isProcessing = false;
  }

  // 添加任务到队列
  addTask(task) {
    this.queue.push(task);
    if (!this.isProcessing) {
      this.processNext();
    }
  }

  // 处理下一个最高优先级任务
  async processNext() {
    if (this.queue.length === 0) {
      this.isProcessing = false;
      return;
    }

    this.isProcessing = true;
    // 找出队列中优先级最高的任务（数值越大优先级越高）
    let highestPriorityIndex = 0;
    for (let i = 1; i < this.queue.length; i++) {
      if (this.queue[i].priority > this.queue[highestPriorityIndex].priority) {
        highestPriorityIndex = i;
      }
    }
    // 取出该任务
    const task = this.queue.splice(highestPriorityIndex, 1)[0];

    try {
      await task.fn();
    } catch (err) {
      console.error('任务执行失败:', err);
    } finally {
      // 任务完成后继续处理下一个
      this.processNext();
    }
  }
}

使用示例：

const queue = new PriorityPromiseQueue();

// 添加低优先级任务（优先级1）
queue.addTask(new Task(() => {
  return new Promise(resolve => {
    setTimeout(() => {
      console.log('低优先级任务完成');
      resolve();
    }, 2000);
  });
}, 1));

// 1秒后添加高优先级任务（优先级10）
setTimeout(() => {
  queue.addTask(new Task(() => {
    return new Promise(resolve => {
      setTimeout(() => {
        console.log('高优先级任务完成');
        resolve();
      }, 1000);
    });
  }, 10));
}, 1000);

// 输出顺序：低优先级任务开始执行 → 1秒后高优先级任务入队 → 低优先级任务完成（2秒时）→ 高优先级任务执行完成（3秒时）

方案二：基于最大堆的高效实现（适合大规模任务） #

当任务数量较多时，数组实现每次遍历找最高优先级任务的时间复杂度为O(n)，效率较低。此时可以用最大堆数据结构维护队列，插入和获取最高优先级任务的时间复杂度均为O(logn)，大幅提升性能。

代码实现：

class Task {
  constructor(fn, priority) {
    this.fn = fn;
    this.priority = priority;
  }
}

// 最大堆实现，用于维护优先级任务
class MaxHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  insert(task) {
    this.heap.push(task);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    let currentIndex = index;
    let parentIndex = this.getParentIndex(currentIndex);
    while (currentIndex > 0 && this.heap[currentIndex].priority > this.heap[parentIndex].priority) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = this.getParentIndex(currentIndex);
    }
  }

  extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return max;
  }

  bubbleDown(index) {
    let currentIndex = index;
    let leftChildIndex = this.getLeftChildIndex(currentIndex);
    let rightChildIndex = this.getRightChildIndex(currentIndex);
    let largestIndex = currentIndex;

    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].priority > this.heap[largestIndex].priority) {
      largestIndex = leftChildIndex;
    }

    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].priority > this.heap[largestIndex].priority) {
      largestIndex = rightChildIndex;
    }

    if (largestIndex !== currentIndex) {
      this.swap(currentIndex, largestIndex);
      this.bubbleDown(largestIndex);
    }
  }

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

class PriorityPromiseQueue {
  constructor() {
    this.heap = new MaxHeap();
    this.isProcessing = false;
  }

  addTask(task) {
    this.heap.insert(task);
    if (!this.isProcessing) {
      this.processNext();
    }
  }

  async processNext() {
    if (this.heap.size() === 0) {
      this.isProcessing = false;
      return;
    }

    this.isProcessing = true;
    const task = this.heap.extractMax();

    try {
      await task.fn();
    } catch (err) {
      console.error('任务执行失败:', err);
    } finally {
      this.processNext();
    }
  }
}

方案对比 #

内容的提问来源于stack exchange，提问作者Ali Reza Riahi