🎏优先队列的JavaScript实现

优先队列中的每个元素都有对应的优先级，优先级最高的元素最先获得服务，优先级相同的元素按照其在优先队列中的顺序得到服务。

操作

• 插入带有优先级的元素
• 取出具有最高优先级的元素
• 查看最高优先级的元素

其它可选的操作：

• 检查优先级高的一批元素
• 清空优先队列
• 批插入一批元素
• 合并多个优先队列
• 调整一个元素的优先级

实现

初级实现

使用有序数组，插入时排序，插入效率为，取出效率为

import Queue from "./Queue";
class QueueElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}
export class PriorityQueue extends Queue {
  constructor() {
    super();
  }
// euqueue 入队
//  重写enqueue，需要加入priority
  enqueue(element, priority) {
  //  根据传入元素，创建QueueElement对象
    const queueElement = new QueueElement(element,priority);
  //  判断队列是否为空
    if (this.isEmpty()) {
    //  如果是空队列，就不管优先级了，直接添加
      this.items.push(queueElement);
    } else {
    //  定义变量记录是否添加新元素
      let added = false;
      for(let i = 0; i < this.items.length; i++) {
      //  让新加入的元素进行优先级比较，priority越小，优先级越大
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i,0, queueElement);
          added = true;
          break;
        }
      }
    //  如果队列中元素都被遍历了，说明优先级最小，插到队列末尾
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }
//  dequeue 出队，从队列中删除前端元素，返回被删除的元素，因为已经插入时就排好序了，所以此时就无需排序
  dequeue() {
    return super.dequeue();
  }
//  peek 查看队列前端元素
  peek() {
    return super.peek();
  }
//  isEmpty 查看队列是否为空
  isEmpty() {
    return super.isEmpty();
  }
//  size 查看队列中元素个数
  size() {
    return super.size();
  }
// clear 清除队列中的元素
  clear() {
    return super.clear();
  }
//  toString 将队列中元素以字符串形式输出
  toString() {
    let result = '';
    for (let item of this.items) {
      result += item.element + '-' + item.priority;
    }
    return result;
  }
}

典型实现

出于性能考虑，优先队列用堆)来实现，具有O(log n)时间复杂度的插入元素性能，O(n)的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为O(log n)，构造二叉树的时间复杂度为O(n log n)。
从计算复杂度的角度，优先级队列等价于排序算法。
有一些特殊的堆)为优先队列的实现提供了额外的性能：二叉堆的插入与提取操作的时间复杂度为O(log n)，并可以常量时间复杂度的peek操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度，[1]，但删除操作的时间复杂度为O(log n)。Brodal queue具有最糟糕情况下的常量复杂度但算法相当复杂因而不具有实用性。
对于整型、浮点型等具有有限值域的元素的数据类型，优先队列有更快的实现。