美文网首页
优先队列

优先队列

作者: 假装会编程 | 来源:发表于2016-10-20 21:37 被阅读0次

一般情况下,队列都需要遵循FIFO原则,但在一些特殊的场合,我们希望队列的出队能够更加智能,不仅仅考虑入队先后顺序,同时还考虑队中元素的优先性,以保障资源能够得到更加科学有效的使用。

要实现优先队列,首先考虑如何区分不同优先级的元素,一种做法是给元素添加优先级标记/属性。

var element = {
  ......
  this.priority = high / medium / low;
  ......
}

其次则是元素出队的实现,已知的方法是在出队方法/函数中添加判断逻辑,返回当前队列中最接近队首且优先级最高的元素;

function dequeue() {
  var index = 0,//最接近队首且优先级最高的元素序号,初始为0(即队首)
      superior = this.data.priority;//当前最高优先级
  //遍历确定出队元素
  for (var i = 1; i < this.data.length; ++i) {
    if (this.data[i].priority > priority) {//若当前遍历元素优先级高于已知最高优先级
      priority = this.data[i].priority;//更新最高优先级
      index = i;//更新出队元素
    }
  }
return this.data.splice(index,1);
}

2017.04.12的更新
也可以考虑使用堆实现优先级队列,入队时调用restore重建堆,形成最大堆,即优先级最高的元素保持在堆顶,出队时弹出堆顶元素,然后调用restore再次重建堆,需要考虑的是如何保持同级元素的FIFO的特性;

相关文章

网友评论

      本文标题:优先队列

      本文链接:https://www.haomeiwen.com/subject/vpqquttx.html