Last active
March 18, 2020 09:47
-
-
Save Prottoy2938/27f45a918a8edbb2510e46cbcbea638e to your computer and use it in GitHub Desktop.
Max Binary Heap implementation in JavaScript
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
//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