priority queue

priorityQueue.js

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

class PriorityQueue {
  constructor() {
    this.data = []
  }

  enqueue(node) {
    let val = node.val
    let priority = node.priority
    if (this.data.length == 0) {
      this.data.push(node)
      return this
    }
    this.data.push(node)
    let index = this.data.length - 1

    while (true) {
      if (index == 0)
        break
      let parentIndex = Math.floor((index - 1) / 2)

      if (this.data[parentIndex].priority > this.data[index].priority) {
        let parent = this.data[parentIndex]
        let temp = this.data[index]
        this.data[index] = parent
        this.data[parentIndex] = temp
      }
      index = parentIndex
    }
    return this
  }

  dequeue() {
    let root = this.data[0]
    let end = this.data[this.data.length - 1]
    this.data[0] = end
    this.data.pop()
    let index = 0

    while (true) {
      let leftChildIndex = index * 2 + 1
      let rightChildIndex = index * 2 + 2
      let swap
      if (leftChildIndex < this.data.length) {
        if (this.data[leftChildIndex].priority < this.data[index].priority) {
          swap = leftChildIndex
        }
      }
      if (rightChildIndex < this.data.length) {
        if (swap != null && this.data[rightChildIndex].priority < this.data[swap].priority) {
          swap = rightChildIndex
        }
        if (swap == null && this.data[rightChildIndex].priority < this.data[index].priority) {
          swap = rightChildIndex
        }
      }
      if (swap == null)
        break
      let temp = this.data[index]
      this.data[index] = this.data[swap]
      this.data[swap] = temp
      index = swap
    }
    return root
  }
}