javascript 之优先队列

大家好，我是 17

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

优先队列至少需要支持下述操作：

• 插入带优先级的元素（insert_with_priority）
• 取出具有最高优先级的元素（pull_highest_priority_element）
• 查看最高优先级的元素（peek）：O(1) 时间复杂度

其它语言一般都有相应的函数，可惜 js 没有，所以补上一个。

class PriorityQueue {
  constructor(compare) {
  
     if(typeof compare !=='function'){
        throw new Error('compare function required!')
     }
  
     this.data = []
     this.compare = compare
    
  }
  //二分查找 寻找插入位置
  search(target) {
    let low = 0, high = this.data.length
    while (low < high) {
      let mid = low + ((high - low) >> 1)
      if (this.compare(this.data[mid], target) > 0) {
        high = mid
      }
      else {
        low = mid + 1
      }
    }
    return low;
  }
  //添加
  push(elem) {
    let index = this.search(elem)
    this.data.splice(index, 0, elem)
    return this.data.length
  }
  //取出最优元素
  pop() {
    return this.data.pop()
  }
  //查看最优元素
  peek() {
    return this.data[this.data.length - 1];
  }
}

先不要看代码实现，把 PriorityQueue 当作黑盒看看怎么使用。

最大值最小值优先

每次取出的是整个队列中的最小值。为了达到这个目的，队列是有序的，且升序排列。

拿实际值演练一下。

let qeen = new PriorityQueue((a, b) => a-b)
queen.push(3);
console.log(queen.data)  //[3]
queen.push(1);
console.log(queen.data)  //[1,3]
qeeun.push(2);
console.log(queen.data)  //[1,2,3]

每次播入新元素，都会自动把元素插入到正确的位置，保持队列按升序排列，关键就在于 (a,b) => a-b 这个 compare 方法 是这经告诉 PriorityQueue 如何插入元素。这个compare 方法和 Array的 sort 方法用的 compare 是一样的,是为了好记，只要会sort 方法，就会用 PriorityQueue

let arr = [1, 3, 2]
//按升序
arr.sort((a, b) => a - b) //  [1,2,3]

//优先队列的数据按升序排列
let qeen = new PriorityQueue((a, b) => a - b)
queen.push(3);
queen.push(2);
queen.push(1);

consolelog(queen.data) //[ 1，2，3 ]

//按降序
arr.sort((a, b) => b - a) //  [3,2,1]
//优先队列的数据按降序排列
let qeen = new PriorityQueue((a, b) => b - a) 

PriorityQueue 是特意采用数组已有的方法名，就是为了好记。

除了 push pop peek，还有 search 方法也是公开的，而且查找速度也是很快的。如果不知道目标元素的 index,只知道值，可以用 search 查找。

注意 search 找到的是播入位置

复杂度

时间复杂度

• pop O(1)
• peek O(1)
• push O(n),
• search O(logn)

有的同学这样写的，没有用 splice 方法

//从小到大排列,播入元素，向前冒泡
function insert(n) {
  this.data.push(n);
  let len = this.data.len
  while (len-- > 0) {
    if (this.data[len] < this.data[len - 1]) {
      //交换
      [this.data[len], this.data[len - 1]] = [this.data[len - 1], this.data[len]]
    }
    else {
      break
    }
  }
}

理由是 既然 splice 方法最后也是 O(n)，我这样也是 O(n)。但实际上 splice 方法在速度比这样循环要快多了。

虽然在插入的时候较慢，但取出数据的时候是 O(1)，取 前 N 个数据的时间也比树快。

如果要优化插入的时间，可以用红黑树，但取出数据后还得维护树， 插入，取（删除）都是 O(logn)。而且用树的话，就不能通过 index 用 O(1) 的时间来找到元素了。

所以当前版本的 PriorityQueue 还是可以优先考虑的。

空间复杂度

data存的值不算，额外的空间为 O(1)

最后提醒一下，PriorityQueue 不是光能存数字，是可以存对象的。只要给出 比较对象的方法即可，和数组的 sort 方法一样。

参考

• 简单易懂的红黑树原理及实现(js)