javascriptpriority-queueheapmin-heapmax-heap

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


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


Solution

  • A few issues in your bubbleUp method:

    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.