Skip to content

Instantly share code, notes, and snippets.

@Prottoy2938
Last active March 18, 2020 09:47
Show Gist options
  • Save Prottoy2938/27f45a918a8edbb2510e46cbcbea638e to your computer and use it in GitHub Desktop.
Save Prottoy2938/27f45a918a8edbb2510e46cbcbea638e to your computer and use it in GitHub Desktop.
Max Binary Heap implementation in JavaScript
//BinaryHeaps are very similar to Binary Tree with some slightly different rules. It has two catagories, Max Binary Heap and Min Binary Heap
//In a Max Binary Heap, parent node is always larger than its child nodes and In a Min Binary Heap, parent node is always smaller than its child node.
//This snippet implementation of Max Binary Heap with JavaScript Arrays.
//Parent idx=n; leftChild idx=[2 * n + 1 ] and rightChild Idx=[2 * n + 2 ]
class MaxBinaryHeap {
constructor() {
this.values = [];
}
//pushes value at the end of the array and bubbles it way up. It finds it's parent ((idx - 1) / 2) and checks if its larger, if it is -it swaps and this circle goes on.
insert(element){
this.values.push(element);
this.bubbleUp();
}
//helper function for insert method
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 <= parent) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
//This method removes the root/the largest value from the list. And makes the very last element of the list it's root.
//Than it sinks down to its childens and does the comparison and finds the largest value and makes it the new root.
extractMax() {
const max = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return max;
}
//helper function for extractMax
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
let loopWillRun = true;
while (loopWillRun) {
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;
}
}
}
//EXAMPLES==============================================================================
const mxBHeap = new MaxBinaryHeap();
mxBHeap.insert(41);
mxBHeap.insert(39);
mxBHeap.insert(33);
mxBHeap.insert(18);
mxBHeap.insert(27);
mxBHeap.insert(12);
mxBHeap.insert(55);
mxBHeap.extractMax();
mxBHeap.extractMax();
export { mxBHeap };
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment