doing a priority queue as a min-heap in javascript. console keeps returning priority is undefined in the while loop. what is the problem? / how to enqueue element to queue?
//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);
}
}
}
A few issues in your bubbleUp
method:
while
loop never updates the variables that are compared in the loop condition.parentIndex
is no longer valid, i.e. when childIndex
is the root, and then exit.Here is a correction:
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);
}
}
For full implementations, have a look at Efficient way to implement Priority Queue in Javascript?, where I have also posted my preferred implementation.