JS数据结构&算法学习——优先队列

优先级队列

我们在了解过队列之后，有没有考虑过优先级队列的事情呢？

概念

我们知道普通的队列想要添加元素，元素会被在队尾入队，但是优先级队列它在考虑添加一个元素的时候会考虑添加数据的优先级，即将我们即将插入数据的优先级与其他数据的优先级一一进行比较，在之后我们就可以得到将要添加的元素在队列中正确的位置。

生活中的应用

1. VIP优先：我们生活中最能体现优先级队列的就是在排队过程中的VIP通道了，当我们在按照队列进行排队的时候，下一个进入的人是VIP，按理说他是应该在队尾添加，但是由于优先级的原因，高于我们这些普通顾客，他就会通过VIP通道被添加到正确的位置
2. 道德优先：在我们正常排队去挂号的时候，是按照队列来进行排队的，但是会有需要紧急救治的病人，这个时候就体现了优先级的特点，医生会优先救治那些需要紧急救治的病人。

程序应用

在之前的队列中有提到过，线程队列是按照线程次序来执行的，这个时候如果按照线程的优先级大小来排列，就是通过优先级队列来执行

封装

在封装优先级队列之前，我们需要考虑的是我们如何进行优先级比较以及比较规则

当我们的普通的队列拿来看的话，我们是无法对其元素进行比较的，所以我们需要每个元素需要额外的一个能表达该元素优先级的值来体现该元素的优先级，这样我们才能对其优先级进行比较并形成优先级队列，封装如下

function priorityQueue() {
    //队列的属性
    function QueueElement(element, priority) {
      this.element = element
      this.priority = priority
    }
    this.items = []
    //队列的相关操作
    priorityQueue.prototype.enqueue = function (element, priority) {
      //1.创建对象
      var QueueElement = new QueueElement(element, priority)
      this.items.push(element)
    }
}
复制代码

大家可以明显的注意到，我们在优先级队列这个类中又声明了一个类，由于元素具有原本的值与优先级两个数据，所以我们需要在类中再声明一个类，之后的操作封装也是在函数中创建新类，其中element为数据，priority为优先级

那么我们现在开始考虑我们如何得去比较并按优先级排序

1. 当队列没有元素，只需要添加元素，无序比较
2. 当队列中有元素，我们需要将添加的元素与前一个数据比较，若小则再比较，直到遇到优先级大的并插入到后面

priorityQueue.prototype.enqueue = function (element, priority) {
      var QueueElement = new QueueElement(element, priority)
      if (this.items.length == 0) {
          this.items.push(QueueElement)
      } else {
          var add = false
          for (let i = 0; i < this.items.length; i++){
              if (QueueElement.priority < this.items[i]){
                  this.items.splice(i,0,QueueElement)
                  add = true
                  break
              }
          }
          if(!add) {
              this.items.push(QueueElement)
          }
      }
}
复制代码

在这里我们首先会进行对队列是否为空判断，可以用自己封装的isEmpty也可以使用length直接进行判断，如果为空则直接插入，接下里如果队列不为空，则声明一个变量表达状态，如果与前面的元素进行比较，优先级都比被添加元素大的话add为false，则执行下面的部分，直接添加到队尾，如果找到了优先级小的元素，则使用splice的方法来进行插入