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
– fubar, Commented Sep 24, 2022 at 22:44

trincot · Accepted Answer · 2022-09-25 07:47:34Z

1

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.

edited Sep 25, 2022 at 7:47

answered Sep 25, 2022 at 7:38

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

AlmostThere Over a year ago

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. stackoverflow.com/questions/73954798/…

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related