Skip to content

Instantly share code, notes, and snippets.

@lucas-janon
Created July 2, 2018 04:01
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lucas-janon/77935c7d285f1c6362442815e76de12b to your computer and use it in GitHub Desktop.
Save lucas-janon/77935c7d285f1c6362442815e76de12b to your computer and use it in GitHub Desktop.
Min heap javascript implementation
class MinHeap {
constructor ({ items } = {}) {
this.heap = items ? [...items] : []
this.length = this.heap.length
}
get () {
return this.heap
}
parent (index) {
return (index - 1) % 2 === 0 ? (index - 1) / 2 : (index - 2) / 2
}
left (index) {
return index * 2 + 1
}
right (index) {
return index * 2 + 2
}
order () {
for (let i = parseInt(this.length / 2, 10); i >= 0; i--) {
this.minHeapify(i)
}
}
push (value) {
this.heap.push(value)
this.length++
let valueIndex = this.length - 1
let parentIndex = this.parent(valueIndex)
let parent = this.heap[parentIndex]
while (parent > value) {
this.swap(valueIndex, parentIndex)
valueIndex = parentIndex
parentIndex = this.parent(parentIndex)
parent = this.heap[parentIndex]
}
}
pop (value) {
this.heap[0] = this.heap[this.length - 1]
this.heap.pop()
this.length--
this.minHeapify(0)
}
minHeapify (index) {
const value = this.heap[index]
const leftSubtreeIndex = index * 2 + 1
const rightSubtreeIndex = index * 2 + 2
const leftSubtree = this.heap[leftSubtreeIndex]
const rightSubtree = this.heap[rightSubtreeIndex]
let smallest = index
if (value > leftSubtree) smallest = leftSubtreeIndex
if (this.heap[smallest] > rightSubtree) smallest = rightSubtreeIndex
if (smallest !== index) {
this.swap(index, smallest)
return this.minHeapify(smallest)
}
}
swap (index1, index2) {
const temp = this.heap[index1]
this.heap[index1] = this.heap[index2]
this.heap[index2] = temp
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment