priority queue question. priority is undefined in while loop. how to enqueue element to queue?

Question

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

One scenario you're not considering is when the heap has only one element. — fubar, Sep 24 '22 at 22:44

trincot · Accepted Answer · 2022-09-25T07:47:34.800

A few issues in your bubbleUp method:

The while loop never updates the variables that are compared in the loop condition.
The processing should detect when 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.

thanks much appreciated, i have a question on how to dequeue-ing if you don't mind looking at it. i know there's no boundaries, but i am updating the variable. https://stackoverflow.com/questions/73954798/min-priority-queue-question-dequeue-doesnt-work-says-undefined-for-priority — AlmostThere, Oct 05 '22 at 14:08

priority queue question. priority is undefined in while loop. how to enqueue element to queue?

1 Answers1