在javascript中将优先级队列作为最小堆。控制台不断返回优先级在while循环中未定义。有什么问题?/如何将元素排队?
//min-heap
class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(value, priority){
let newNode = new Node(value, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp(){
let childIndex = this.values.length - 1;
let parentIndex = Math.floor((childIndex - 1) / 2);
let childElement = this.values[childIndex].priority;
let parentElement = this.values[parentIndex].priority;
while(childElement < parentElement){
let temp = this.values[childIndex];
this.values[childIndex] = this.values[parentIndex];
this.values[parentIndex] = temp;
childIndex = parentIndex;
parentIndex = Math.floor((childIndex - 1) / 2);
}
}
}
bubbleUp
方法中的一些问题:
while
循环从不更新循环条件中比较的变量。父母索引
不再有效,即当儿童索引
是根时,然后退出。这里有一个更正:
bubbleUp(){
let childIndex = this.values.length - 1;
let parentIndex = Math.floor((childIndex - 1) / 2);
while (childIndex > 0 && this.values[childIndex].priority < this.values[parentIndex].priority){
let temp = this.values[childIndex];
this.values[childIndex] = this.values[parentIndex];
this.values[parentIndex] = temp;
childIndex = parentIndex;
parentIndex = Math.floor((childIndex - 1) / 2);
}
}
对于完整的实现,请查看在Javascript中实现优先级队列的有效方法?,我还发布了我的首选实现。