class PriorityQueue {
constructor() {
this.values = []
}
enqueue(value, priority) {
if(this.values.length === 0) {
this.values.push({value: value, priority: priority})
return this.values;
}
this.values.push({value, priority});
this.bubbleUp(this.values);
}
bubbleUp(values) {
let childIndex = values.length-1;
let parentIndex;
parentIndex = Math.floor((childIndex-1)/2);
let childNode, parentNode, temp;
console.log(parentIndex, childIndex);
console.log(values[parentIndex].priority, values[childIndex].priority)
while ((values[childIndex].priority) < (values[parentIndex].priority)) {
childNode = values[childIndex];
parentNode = values[parentIndex];
temp = childNode;
childNode = parentNode;
parentNode = temp;
values[childIndex] = childNode;
values[parentIndex] = parentNode;
childIndex = parentIndex;
parentIndex = Math.floor((childIndex-1)/2);
}
return values;
}
}
The above is my implementation of priority queue using JavaScript.
I am storing the data in an array containing nodes that are objects like this
{value: "something", priority: 1}
When I try to add the second node using the enqueue method, I get an error in the while condition.
Uncaught TypeError: Cannot read properties of undefined (reading 'priority')
I can clearly see the priority values of the nodes in the previous console.log statement. I am unable to figure out why the loop condition is failing with an error which says I am trying to read properties of undefined.
Any help will be appreciated.
Check this,
class Node {
constructor(data, priority) {
this.data = data;
this.priority = priority;
}
}
class PQ {
constructor() {
//Initialing the array heap and adding a dummy element at index 0
this.heap = [];
}
getMin() {
//Accessing the min element at index 1 in the heap array
return this.heap[0];
}
enqueue(data, priority) {
let newNode = new Node(data, priority);
this.heap.push(newNode);
let currentIndex = this.heap.length - 1;
let parentIndex = Math.round(currentIndex / 2) - 1;
while (
currentIndex > 0 &&
this.heap[parentIndex].priority > this.heap[currentIndex].priority
) {
[this.heap[parentIndex], this.heap[currentIndex]] = [
this.heap[currentIndex],
this.heap[parentIndex],
];
currentIndex = parentIndex;
}
}
dequeue() {
//Smallest element is at the index 1 in the heap array
let smallest = this.heap[0];
if (this.heap.length === 1) {
//If there are only two elements in the array, we directly splice out the first element
this.heap.splice(0, 1);
}
//When there are more than two elements in the array, we put the right most element at the
//first position and start comparing nodes with the child nodes
if (this.heap.length >= 2) {
this.heap[0] = this.heap[this.heap.length - 1];
this.heap.splice(this.heap.length - 1);
if (this.heap.length === 2) {
if (this.heap[0].priority > this.heap[1].priority) {
[this.heap[0], this.heap[1]] = [this.heap[1], this.heap[0]];
}
return smallest;
}
let current = 0;
let leftChildIndex = current * 2 + 1;
let rightChildIndex = current * 2 + 2;
while (
this.heap[leftChildIndex] &&
this.heap[rightChildIndex] &&
(this.heap[current].priority > this.heap[leftChildIndex].priority ||
this.heap[current].priority > this.heap[rightChildIndex].priority)
) {
if (this.heap[leftChildIndex].priority < this.heap[rightChildIndex].priority) {
[this.heap[current], this.heap[leftChildIndex]] = [
this.heap[leftChildIndex],
this.heap[current],
];
current = leftChildIndex;
} else {
[this.heap[current], this.heap[rightChildIndex]] = [
this.heap[rightChildIndex],
this.heap[current]
];
current = rightChildIndex;
}
leftChildIndex = current * 2 + 1;
rightChildIndex = current * 2 + 2;
}
}
return smallest;
}
}
const pq = new PQ();
pq.enqueue(3, 2);
pq.enqueue(4, 5);
pq.enqueue(31, 1);
pq.enqueue(6, 3);
console.log(pq.heap);
console.log(pq.dequeue());
console.log(pq.dequeue());
console.log(pq.dequeue());
console.log(pq.dequeue());