优先级队列

一、概念


优先级队列的特点：

• 优先级队列，在插入一个元素的时候会考虑该数据的优先级。
• 和其他数据优先级进行比较。
• 比较完成后，可以得出这个元素在队列中正确的位置。
• 其他处理方式和基本队列的处理方式一样。

优先级队列主要考虑的问题

• 每个元素不再只是一个数据，而且包含数据的优先级。
• 在添加方式中，根据优先级放入正确的位置。

优先级队列的应用

• 登机顺序（头等舱、商务舱、经济舱）
• 急诊科（严重患者，普通排号患者）
• 计算机中，通过 优先级队列 来重新排序队列中任务的顺序

二、属性和方法

队列的方法（6个）：

• enqueue(): 向队列尾部添加一个或多个新的项
• dequeue(): 移出队列的第一项，并返回被移出的元素
• front(): 返回队列中第一个元素
• isEmpty(): 如果队列中不包含任何元素，返回true，否则返回false
• size(): 返回队列包含的元素个数
• toString(): 将队列中的内容，转换成字符串形式

代码实现

/***************  优先级队列的封装 ***********/
function PriorityQueue() {

  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }

  // 属性
  this.items = [];

  // 插入方法
  PriorityQueue.prototype.enqueue = function (element, priority) {
    // 1.创建QueueElement 对象
    let queueElement = new QueueElement(element, priority);

    // 2.判断队列是否为空
    if (this.items.length === 0) {
      this.items.push(queueElement);
    } else {
      let added = false;
      for (let i = 0; i < this.items.length; i++) {
        const item = this.items[i];
        if (queueElement.priority < item.priority) {
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }

  // 移出队列的第一项（排在队列最前面的）项，并返回被移出的元素
  PriorityQueue.prototype.dequeue = function () {
    return this.items.shift();
  }

  // 返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
  // 队列不做任何变动，不移除元素，只返回元素
  PriorityQueue.prototype.front = function () {
    return this.items[0]
  }

  // 如果队列中不包含任何元素，返回true，否则返回false
  PriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0
  }

  // 返回队列包含的元素个数，与数组的length属性类似
  PriorityQueue.prototype.size = function () {
    return this.items.length;
  }

  // 将队列中的内容，转换成字符串形式
  PriorityQueue.prototype.toString = function () {
    return this.items.toString();
  }

}

测试：

const pq = new PriorityQueue();
pq.enqueue('aa', 100)
pq.enqueue('bb', 200)
pq.enqueue('cc', 50)
pq.enqueue('dd', 80)
pq.enqueue('ee', 60)

console.log(pq)