min priority queue question. dequeue doesn't work. says undefined for priority

Question

this is a min-priority queue in javascript. i can't get dequeue to work. it says in console TypeError: Cannot read properties of undefined (reading 'priority'). i'm able to insert all the nodes into an array. when i console the array after dequeue-ing, it returns the correct number of nodes. i just can't return the oldNode after the 1st oldNode.

//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);

    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);
    }
  }
  dequeue(){
    if(!this.values.length) return null;
    //swap root and highest number element
    this.swap(0, this.values.length - 1);
    let oldNode = this.values.pop();

    let parent = 0, childLeft = 1, childRight = 2;
    let min = Math.min(this.values[childLeft].priority, this.values[childRight].priority);

    while(this.values[parent].priority > min){
      let child = this.values[childLeft].priority === min ? childLeft : childRight;
      this.swap(parent, child);
      parent = child;

      //get children of current parent
      childLeft = parent * 2 + 1;
      childRight = parent * 2 + 2;

      min = Math.min(this.values[childLeft].priority, this.values[childRight].priority);
    }
    return oldNode;
  }
  swap(index1, index2){
    [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]];
  }
}

class Node{
  constructor(value, priority){
    this.value = value;
    this.priority = priority;
  }
}

Answer 1

There are a few issues:

• The swap method isn't swapping: the indexes should be reversed on one of the two sides of the assignment.

• The dequeue method is making accesses to the values array that are beyond its length. For instance, if there is only one element in the heap (after the pop), then childLeft and childRight are both out of range, and this.values[childLeft].priority will attempt to get the priority property from an undefined value, which leads to the error you got. But even if the values array has more entries, this situation can occur in the loop as well. When childLeft and childRight get updated values, the last statement in the loop body will not check whether this indices are still within the valid range.

To avoid the code repetition you already have (the two statements before the loop look the similar to the last two statements in the loop body), I would actually make that range check your loop condition, and make the condition you currently use a check that is made half-way the loop body.

Here is a correction:

  dequeue(){
    if (!this.values.length) return null;
    //swap root and highest number element
    this.swap(0, this.values.length - 1);
    let oldNode = this.values.pop();

    let parent = 0;
    while (parent * 2 + 1 < this.values.length) { // While the parent has at least one child
        // get child(ren) of current parent
        let child = parent * 2 + 1; // right child is just next to it. No need for an extra variable.
        // if there is a right child(!), take it when it has a lesser rank than the left child
        if (child + 1 < this.values.length && this.values[child].priority > this.values[child + 1].priority) {
            child++; // Choose the right child, as it has the lesser rank
        }
        // Exit when parent has a lesser rank than its child(ren)
        if (this.values[parent].priority < this.values[child].priority) break;
        this.swap(parent, child);
        parent = child;
    }
    return oldNode;
  }
  swap(index1, index2){
    [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]]; // fixed
  }