Last active
November 12, 2022 15:48
-
-
Save SparrowMike/0cb6e6054f1287da4b4a2769ead5bbfb to your computer and use it in GitHub Desktop.
This file contains 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 MaxBinaryHeap { | |
constructor() { | |
this.values = [41, 39, 33, 18, 27, 12]; | |
} | |
insert(val) { | |
this.values.push(val); | |
this.bubbleUp(val); | |
return this.values; | |
} | |
bubbleUp(val) { | |
let index = this.values.length - 1; | |
while(index > 0) { | |
let parentIdx = Math.floor((index - 1) / 2); | |
let parent = this.values[parentIdx]; | |
if (val <= parent) break; | |
this.values[parentIdx] = val; | |
this.values[index] = parent; | |
index = parentIdx; | |
} | |
} | |
extractMax() { | |
const max = this.values[0] | |
const end = this.values.pop(); | |
if (this.values.length > 0) { | |
this.values[0] = end; | |
this.bubbleDown(); | |
} | |
return max; | |
} | |
bubbleDown() { | |
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 > element) { | |
swap = leftChildIdx; | |
} | |
} | |
if (rightChildIdx < length) { | |
rightChild = this.values[rightChildIdx]; | |
if ( | |
(swap === null && rightChild > element) || | |
(swap !== null && rightChild > leftChild) | |
) { | |
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; | |
} | |
} | |
// Priority Queue | |
class MinBinaryHeap { | |
constructor() { | |
this.values = []; | |
} | |
enqueue(val, priority) { | |
let newNode = new Node(val, priority) | |
this.values.push(newNode); | |
this.bubbleUp(newNode); | |
return this.values; | |
} | |
bubbleUp(node) { | |
let index = this.values.length - 1; | |
while(index > 0) { | |
let parentIdx = Math.floor((index - 1) / 2); | |
let parent = this.values[parentIdx]; | |
if (node.priority >= parent.priority) break; | |
this.values[parentIdx] = node; | |
this.values[index] = parent; | |
index = parentIdx; | |
} | |
} | |
dequeue() { | |
const min = this.values[0] | |
const end = this.values.pop(); | |
if (this.values.length > 0) { | |
this.values[0] = end; | |
this.bubbleDown(); | |
} | |
return min; | |
} | |
bubbleDown() { | |
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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment