| class Node { | |
| constructor(val,priority) { | |
| this.val = val; | |
| this.priority = priority; | |
| } | |
| } | |
| class PriorityQueue { | |
| constructor() { | |
| this.values = [] | |
| } | |
| bubbleUp() { | |
| let index = this.values.length - 1; | |
| let parentIndex = Math.floor((index - 1) / 2); | |
| while(this.values[parentIndex] && this.values[parentIndex]['priority'] > this.values[index]['priority']){ | |
| let temp = this.values[index]; | |
| this.values[index]= this.values[parentIndex]; | |
| this.values[parentIndex] = temp; | |
| index = parentIndex; | |
| parentIndex = Math.floor((index - 1) / 2); | |
| } | |
| } | |
| bubbleDown() { | |
| let index = 0; | |
| let leftChildIndex,rightChildIndex; | |
| while(true) { | |
| leftChildIndex = (2 * index) + 1; | |
| rightChildIndex = (2 * index) + 2; | |
| let swappedIndex = null; | |
| if(leftChildIndex < this.values.length) { | |
| if(this.values[leftChildIndex]['priority'] < this.values[index]['priority']) { | |
| swappedIndex = leftChildIndex | |
| } | |
| } | |
| if(rightChildIndex < this.values.length) { | |
| if(swappedIndex && this.values[rightChildIndex]['priority'] < this.values[swappedIndex]['priority']){ | |
| swappedIndex = rightChildIndex; | |
| } else if(!swappedIndex && this.values[rightChildIndex]['priority'] < this.values[index]['priority']) { | |
| swappedIndex = rightChildIndex; | |
| } | |
| } | |
| if(swappedIndex) { | |
| let temp = this.values[index]; | |
| this.values[index] = this.values[swappedIndex]; | |
| this.values[swappedIndex] = temp; | |
| index = swappedIndex; | |
| } else { | |
| break; | |
| } | |
| } | |
| } | |
| dequeue() { | |
| let oldMax = this.values[0]; | |
| let newMax = this.values.pop(); | |
| if(this.values.length > 0) { | |
| this.values[0] = newMax; | |
| this.bubbleDown() | |
| } | |
| return oldMax | |
| } | |
| enqueue(val,priority) { | |
| let newNode = new Node(val,priority) | |
| this.values.push(newNode); | |
| this.bubbleUp(); | |
| return this; | |
| } | |
| } | |
| const priorityQueue = new PriorityQueue(); | |
| priorityQueue.enqueue("low fever",3) | |
| priorityQueue.enqueue("concussion",2) // not gurantee order if sample priority | |
| priorityQueue.enqueue("broken arm",2)// not gurantee order if sample priority | |
| priorityQueue.enqueue("Accident",1) | |
| priorityQueue.enqueue("Gun Shot",0) |