Hey guys, I couldn’t figure out what is wrong about my implementation of remove in a max heap. I can’t pass the last test, even though my code behaves correctly in my tests. I wish there was a way to see how fcc tested the methods behind the scenes.
The remove method removes the greatest element from the max heap while maintaining the max heap property.
My Code:
var MaxHeap = function () {
// change code below this line
this.arr = [null];
this.insert = function (val) {
this.arr.push(val);
let i = this.arr.length - 1;
let parentIndex = Math.floor(i / 2);
// console.log(`---i: ${i}`)
// console.log(`p: ${parentIndex}`)
while (parentIndex > 0 && this.arr[i] > this.arr[parentIndex]) {
// console.log(`Swapping bc ${this.arr[i]} > ${this.arr[parentIndex]}`)
let temp = this.arr[i];
this.arr[i] = this.arr[parentIndex];
this.arr[parentIndex] = temp;
i = parentIndex;
parentIndex = Math.floor(i / 2);
// console.log(`New i: ${i}`);
}
}
this.remove = function () {
let valueToRemove = this.arr[1];
let lastVal = this.arr.pop();
let length = this.arr.length;
// console.log(`Array length:${length}`);
let i = 1; // pointer to the moving value
this.arr[i] = lastVal;
let iIsNotLastLevel = (this.arr[2 * i] !== undefined);
let parentIsSmallerThanChildren = this.arr[i] < this.arr[2 * i] || this.arr[i] < this.arr[2 * i + 1]
while (iIsNotLastLevel && parentIsSmallerThanChildren) {
// console.log(`--iIsNotLastLevel: ${iIsNotLastLevel}`);
console.log(`\ni:${i} | ${this.arr}`);
if (this.arr[2 * i] > this.arr[2 * i + 1]) {
console.log(`Left child is bigger than right: ${this.arr[2 * i]} > ${this.arr[2 * i + 1]}`);
let temp = this.arr[2 * i];
this.arr[2 * i] = this.arr[i];
this.arr[i] = temp;
i = 2 * i;
} else {
console.log(`Left child is smaller than right: ${this.arr[2 * i]} < ${this.arr[2 * i + 1]}`);
let temp = this.arr[2 * i + 1];
this.arr[2 * i + 1] = this.arr[i];
this.arr[i] = temp;
i = 2 * i + 1;
}
console.log(`New i:${i} | ${this.arr}`);
iIsNotLastLevel = (this.arr[2 * i] !== undefined);
// console.log(`-iIsNotLastLevel: ${iIsNotLastLevel}`);
parentIsSmallerThanChildren = this.arr[i] < this.arr[2 * i] || this.arr[i] < this.arr[2 * i + 1]
// console.log(`-parentIsSmallerThanChildren: ${parentIsSmallerThanChildren}`);
}
// console.log(`Returning ${valueToRemove}`)
return valueToRemove;
}
this.print = function () {
console.log(this.arr);
return this.arr;
}
// change code above this line
};
let mh = new MaxHeap();
// mh.insert(5);
// mh.insert(3);
// mh.insert(7);
// mh.insert(9);
for (let index = 7; index > 1; index--) {
const element = index;
mh.insert(element);
}
mh.print();
mh.remove();
mh.print();