Skip to content

Instantly share code, notes, and snippets.

@praveenKajla
Created October 20, 2017 12:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save praveenKajla/d6cc81f8a5fadefc92e0471d4a2161ed to your computer and use it in GitHub Desktop.
Save praveenKajla/d6cc81f8a5fadefc92e0471d4a2161ed to your computer and use it in GitHub Desktop.
Minimum heap in Javascript => es6
class minHeap{
constructor(capacity){
this.heapSize = -1;
this.heap = Array(capacity).fill(-1)
}
insert(value){
if(this.heapSize+1==this.heap.length){
throw "Overflow Size"
}
this.heap[this.heapSize+1] = value
this.heapSize = this.heapSize + 1
this.siftUp(this.heapSize);
}
swap(i,j){
[this.heap[i],this.heap[j]] = [this.heap[j],this.heap[i]]
}
siftDown(index){
let minIndex = index
let n = this.heap.length
let lc = 2*index + 1
if(lc<=n-1 && this.heap[lc]<this.heap[minIndex])minIndex=lc
let rc = 2*index + 2
if(rc<=n-1 && this.heap[lc]<this.heap[minIndex])minIndex=rc
if(minIndex != index){
this.swap(index,minIndex)
this.siftDown(minIndex)
}
}
siftUp(index){
let parent = Math.ceil((index-1)/2)
while(index>0 && this.heap[parent]>this.heap[index]){
this.swap(index,parent)
index = parent
parent = Math.ceil((index-1)/2)
}
}
extractMin(){
result = this.heap[0]
this.heap[0] = this.heap[this.heapSize]
this.heapSize = this.heapSize - 1
this.siftDown(0)
return result
}
}
let mh = new minHeap(5)
mh.insert(4)
mh.insert(23)
mh.insert(8)
mh.insert(3)
mh.insert(6)
console.log(mh)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment