Last active
August 16, 2020 17:18
-
-
Save jasterix/019bd8e41844aca9b46756f8bcd11962 to your computer and use it in GitHub Desktop.
Implementing a priority queue with a binary heap
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class PriorityQueue { | |
constructor(){ | |
this.values = []; | |
} | |
enqueue(val, priority){ | |
let newNode = new Node(val, priority); | |
this.values.push(newNode); | |
this.bubbleUp(); | |
} | |
bubbleUp(){ | |
let idx = this.values.length - 1; | |
const element = this.values[idx]; | |
while(idx > 0){ | |
let parentIdx = Math.floor((idx - 1)/2); | |
let parent = this.values[parentIdx]; | |
if(element.priority >= parent.priority) break; | |
this.values[parentIdx] = element; | |
this.values[idx] = parent; | |
idx = parentIdx; | |
} | |
} | |
dequeue(){ | |
const min = this.values[0]; | |
const end = this.values.pop(); | |
if(this.values.length > 0){ | |
this.values[0] = end; | |
this.sinkDown(); | |
} | |
return min; | |
} | |
sinkDown(){ | |
let idx = 0; | |
const length = this.values.length; | |
const element = this.values[0]; | |
while(true){ | |
let leftChildIdx = 2 * idx + 1; | |
let rightChildIdx = 2 * idx + 2; | |
let leftChild,rightChild; | |
let swap = null; | |
if(leftChildIdx < length){ | |
leftChild = this.values[leftChildIdx]; | |
if(leftChild.priority < element.priority) { | |
swap = leftChildIdx; | |
} | |
} | |
if(rightChildIdx < length){ | |
rightChild = this.values[rightChildIdx]; | |
if( | |
(swap === null && rightChild.priority < element.priority) || | |
(swap !== null && rightChild.priority < leftChild.priority) | |
) { | |
swap = rightChildIdx; | |
} | |
} | |
if(swap === null) break; | |
this.values[idx] = this.values[swap]; | |
this.values[swap] = element; | |
idx = swap; | |
} | |
} | |
} | |
class Node { | |
constructor(val, priority){ | |
this.val = val; | |
this.priority = priority; | |
} | |
} | |
let ER = new PriorityQueue(); | |
ER.enqueue("common cold",5) | |
ER.enqueue("gunshot wound", 1) | |
ER.enqueue("high fever",4) | |
ER.enqueue("broken arm",2) | |
ER.enqueue("glass in foot",3) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment