Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
remove() {
/* Smallest element is at the index 1 in the heap array */
let smallest = this.heap[1]
/* When there are more than two elements in the array, we put the right most element at the first position
and start comparing nodes with the child nodes
*/
if (this.heap.length > 2) {
this.heap[1] = this.heap[this.heap.length-1]
this.heap.splice(this.heap.length - 1)
if (this.heap.length === 3) {
if (this.heap[1] > this.heap[2]) {
[this.heap[1], this.heap[2]] = [this.heap[2], this.heap[1]]
}
return smallest
}
let current = 1
let leftChildIndex = current * 2
let rightChildIndex = current * 2 + 1
while (this.heap[leftChildIndex] &&
this.heap[rightChildIndex] &&
(this.heap[current] > this.heap[leftChildIndex] ||
this.heap[current] > this.heap[rightChildIndex])) {
if (this.heap[leftChildIndex] < this.heap[rightChildIndex]) {
[this.heap[current], this.heap[leftChildIndex]] = [this.heap[leftChildIndex], this.heap[current]]
current = leftChildIndex
} else {
[this.heap[current], this.heap[rightChildIndex]] = [this.heap[rightChildIndex], this.heap[current]]
current = rightChildIndex
}
leftChildIndex = current * 2
rightChildIndex = current * 2 + 1
}
}
if (this.heap[rightChildIndex] === undefined && this.heap[leftChildIndex] < this.heap[current]) {
[this.heap[current], this.heap[leftChildIndex]] = [this.heap[leftChildIndex], this.heap[current]]
}
/* If there are only two elements in the array, we directly splice out the first element */
else if (this.heap.length === 2) {
this.heap.splice(1, 1)
} else {
return null
}
return smallest
}
@rhigdon
Copy link

rhigdon commented Jul 6, 2020

Wouldn't current, rightChildIndex and leftChildIndex be undefined at line 40?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment