Last active
June 21, 2020 15:25
-
-
Save johnnyeric/d1ad07e6927213a993effd888590922b to your computer and use it in GitHub Desktop.
Min Heap JavaScript implementation
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
// Based on AlgoExpert's version | |
class MinHeap { | |
heap = null; | |
constructor(array) { | |
this.heap = array; | |
this.buildHeap(); | |
} | |
buildHeap() { | |
const firstParentIndex = Math.floor((this.heap.length - 2) / 2); | |
for (let currentIndex = firstParentIndex; currentIndex >= 0; currentIndex--) { | |
this.siftDown(currentIndex, this.heap.length); | |
} | |
} | |
siftDown(currentIndex, endIndex) { | |
let childOneIndex = currentIndex * 2 + 1; | |
while (childOneIndex <= endIndex) { | |
let childTwoIndex = -1; | |
if (currentIndex * 2 + 2 <= endIndex) { | |
childTwoIndex = currentIndex * 2 + 2; | |
} | |
let indexToSwap = childOneIndex; | |
if (childTwoIndex > -1 && this.heap[childTwoIndex] < this.heap[childOneIndex]) { | |
indexToSwap = childTwoIndex; | |
} | |
if (this.heap[indexToSwap] < this.heap[currentIndex]) { | |
this.swap(currentIndex, indexToSwap); | |
currentIndex = indexToSwap; | |
childOneIndex = currentIndex * 2 + 1; | |
} else { | |
return; | |
} | |
} | |
} | |
siftUp() { | |
let currentIndex = this.heap.length - 1; | |
let parentIndex = Math.floor((currentIndex - 1) / 2); | |
while (currentIndex >= 0 && this.heap[currentIndex] < this.heap[parentIndex]) { | |
this.swap(currentIndex, parentIndex); | |
currentIndex = parentIndex; | |
parentIndex = Math.floor((currentIndex - 1) / 2); | |
} | |
} | |
remove() { | |
this.swap(0, this.heap.length - 1); | |
const peek = this.heap.pop(); | |
this.siftDown(0, this.heap.length - 1); | |
return peek; | |
} | |
peek() { | |
if (this.heap.length == 0) { | |
return -1; | |
} | |
return this.heap[0]; | |
} | |
insert(value) { | |
this.heap.push(value); | |
this.siftUp(); | |
} | |
swap(i,j) { | |
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]] | |
} | |
isEmpty() { | |
return this.heap.length === 0; | |
} | |
} | |
const heap = new MinHeap([]); | |
heap.insert(9); | |
heap.insert(4); | |
heap.insert(20); | |
heap.insert(2); | |
heap.insert(3); | |
console.log(heap.peek()); | |
heap.insert(1); | |
console.log(heap.peek()); | |
console.log(heap.remove()); | |
console.log(heap.peek()); | |
console.log(heap.isEmpty()); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment