Data Structures: Remove an Element from a Max Heap
Hi,
remove() method fails on test but it is works at expected… Am I forget anything?
my code
class Node {
constructor (value) {
this.value = value;
};
};
class MaxHeap {
constructor() {
this.heap = [null];
};
insert(value) {
const newNode = new Node(value);
this.heap.push(newNode);
let currentNodeIndex = this.heap.length - 1,
currentNodeParentIndex = Math.floor(currentNodeIndex -1 / 2)
;
while (this.heap[currentNodeParentIndex] &&
newNode.value > this.heap[currentNodeParentIndex].value
) {
const parent = this.heap[currentNodeParentIndex];
this.heap[currentNodeParentIndex] = newNode;
this.heap[currentNodeIndex] = parent;
currentNodeIndex = currentNodeParentIndex;
currentNodeParentIndex = Math.floor(currentNodeIndex / 2);
}
};
print() {
let result = [];
for (let i = 1; i < this.heap.length; i ++) {
result.push(this.heap[i].value);
}
return result;
};
remove() {
if (this.heap.length < 3) {
const toReturn = this.heap.pop();
this.heap[0] = null;
return toReturn;
}
const toRemove = this.heap[1]; // first element stored to toRemoved
this.heap[1] = this.heap.pop(); // first element redeclared with the last and last deleted
let currentIndex = 1;
let [left, right] = [2 * currentIndex, 2 * currentIndex + 1]
let currentChildIndex = this.heap[right] && this.heap[right].value > this.heap[left].value
? right
: left
;
while (this.heap[currentChildIndex]
&& this.heap[currentIndex].value < this.heap[currentChildIndex].value
) {
let currentNode = this.heap[currentIndex],
currentChildNode = this.heap[currentChildIndex]
;
this.heap[currentChildIndex] = currentNode;
this.heap[currentIndex] = currentChildNode;
}
return toRemove;
};
};
const myMaxHeap = new MaxHeap;
myMaxHeap.insert(6);
myMaxHeap.insert(22);
myMaxHeap.insert(30);
myMaxHeap.insert(37);
myMaxHeap.insert(63);
myMaxHeap.insert(48);
myMaxHeap.insert(42);
myMaxHeap.insert(76);
console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
//console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
console.log(myMaxHeap.print());