美文网首页程序员
学习Javascript数据结构与算法 — 优先队列

学习Javascript数据结构与算法 — 优先队列

作者: SeaseeYoul | 来源:发表于2017-06-14 21:56 被阅读74次
上一篇文章我们讲了队列

队列:http://www.jianshu.com/p/9a35962d5ad5

这一章我们看一看优先队列。优先队列即在队列的基础上多了一个优先级,我们选择一个对象用来存储队列的每一个元素,使用一个属性来存储元素的优先级。存储整个优先队列我们还是使用数组。
实现:

<code>
function priorityQueue(){
var items = [];
function priorityQueueElement(element,priority){
this.element = element;
this.priority = priority;
}
this.enqueue = function(element,priority){
var Node = new priorityQueueElement(element,priority);
if(items.length == 0){
items.push(Node)
}else{
var added = false;
for(var i=0;i<items.length;i++){
if(Node.priority < items[i].priority){
items.splice(i,0,Node);
added = true;
break;
}
}
if(!added){
items.push(Node);
}
}
}
this.print =function(){
console.log(items);
}
}
var pQ = new priorityQueue();
pQ.enqueue("a",1);
pQ.enqueue("b",2);
pQ.enqueue("c",3);
pQ.enqueue("d",1);
pQ.print();

</code>

在上述代码中打印结果应该是:

[ priorityQueueElement { element: 'a', priority: 1 },
priorityQueueElement { element: 'd', priority: 1 },
priorityQueueElement { element: 'b', priority: 2 },
priorityQueueElement { element: 'c', priority: 3 } ]

这样的一个数组,其中每一个元素都是一个 priorityQueueElement 对象。

叩叩叩(手动敲黑板),划重点:

  1. 使用数组存取元素,
  2. 使用 priorityQueueElement 辅助类来创建一个带有优先级的元素。
  3. 每次入队时需要提供元素本身的值(this.element),以及元素本身的优先级(this.priority);通过这两个属性,我们可以创建一个带有优先级的元素。
  4. 如果保存队列的数组是空数组,我们直接 push 进去。
  5. 如果数组不为空,我们先声明一个变量用来存储是否入队的状态,开始遍历数组,如果遇到一个元素的优先级大于需要入队的元素,那么我们把当前元素插入这个元素之前,使用 splice 方法。
  6. 如果遍历玩一遍都没有发现有元素大于新元素,那么我们把新元素push到结尾。

进度有点慢,明天更新,循环队列。~~

相关文章

网友评论

    本文标题:学习Javascript数据结构与算法 — 优先队列

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