Created
October 27, 2020 22:48
-
-
Save ivanzusko/99dcd309a86d6bc4646cbd55e08dfbbe to your computer and use it in GitHub Desktop.
PriorityQueue
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
| /* PriorityQueue */ | |
| /** | |
| * best & avarage worst | |
| * insertion - O(log n) O(log n) | |
| * removal - O(log n) O(log n) | |
| * searching - O(n) O(n) | |
| */ | |
| function PriorityQueue () { | |
| let nodes = []; | |
| function Node (element, priority) { | |
| this.element = element; | |
| this.priority = priority; | |
| } | |
| this.enqueue = function (element, priority) { | |
| const node = new Node(element, priority); | |
| nodes.push(node); | |
| bubbleUp(); | |
| } | |
| this.dequeue = function () { | |
| const max = nodes[0]; | |
| const last = nodes.pop(); | |
| if (!this.isEmpty()) { | |
| nodes[0] = last; | |
| sinkDown(); | |
| } | |
| return max; | |
| } | |
| function bubbleUp () { | |
| let index = nodes.length - 1; | |
| const current = nodes[index]; | |
| while (index > 0) { | |
| let parentIndex = Math.floor((index - 1) / 2); | |
| let parent = nodes[parentIndex]; | |
| if (current.priority >= parent.priority) break; | |
| [nodes[index], nodes[parentIndex]] = [nodes[parentIndex], nodes[index]]; | |
| index = parentIndex; | |
| } | |
| } | |
| function sinkDown () { | |
| let index = 0; | |
| const length = nodes.length; | |
| const current = nodes[0]; | |
| while (true) { | |
| let leftChildIndex = index * 2 + 1; | |
| let rightChildIndex = index * 2 + 2; | |
| let leftChild, rightChild; | |
| let swap = null; | |
| if (leftChildIndex < length) { | |
| leftChild = nodes[leftChildIndex]; | |
| if (leftChild.priority < current.priority) { | |
| // we decide where will swap | |
| swap = leftChildIndex; | |
| } | |
| } | |
| if (rightChildIndex < length) { | |
| rightChild = nodes[rightChildIndex]; | |
| if ( | |
| // if we swaped but right is smaller | |
| (swap !== null && rightChild.priority < leftChild.priority)|| | |
| // if we didn't swap with left, we should swap right | |
| (swap === null && rightChild.priority < current.priority) | |
| ) { | |
| swap = rightChildIndex; | |
| } | |
| } | |
| if (swap === null) break; | |
| // swap values like this: | |
| /** | |
| * values[index] = values[swap]; | |
| * values[swap] = element; | |
| */ | |
| // or like this: | |
| [nodes[index], nodes[swap]] = [nodes[swap], nodes[index]]; | |
| // set new index | |
| index = swap; | |
| } | |
| } | |
| this.isEmpty = function () { | |
| return nodes.length === 0; | |
| } | |
| this.getValues = function () { | |
| return JSON.parse(JSON.stringify(nodes, null, 2)); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment