Data Structures: Remove an Element from a Max Heap

#1

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();
#2

I’m not sure if you figured this out yet, but you also need to cater for when there is only one root element in the heap. In that case the root will be popped from the array and returned. No further action is required. Right now, when you set this.arr[i] = lastVal; it is reseting the root element to the removed element.

1 Like
#3

Thank you for your help. Along with the 2 base cases, I also forgot to check whether the right-child existed when swapping down the elements.

Here is the improved code if anyone needs it.

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 () {
        // Base Case 1: No element initially
        if (this.arr.length === 1) {
            return null;
        }
        let valueToRemove = this.arr[1];
        let lastVal = this.arr.pop(); 
        // Base Case 2: No element left after remove 
        if (this.arr.length === 1) {
            return valueToRemove;
        }

        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] || this.arr[2 * i + 1] === undefined) {
                // 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(9)
mh.insert(6)
mh.insert(0)
mh.insert(2)
mh.insert(3)
// for (let i = 5; i < 10; i++) {
//     const element = Math.floor(Math.random() * 10);
//     mh.insert(element);
// }
mh.print();
mh.remove();
mh.print();
mh.remove();
mh.print();
mh.remove();
mh.print();
mh.remove();
mh.print();
mh.remove();
mh.print();
mh.remove();
mh.print();
1 Like
#4

You are welcome! To make your code more cleaner, since ES6 you can swap variables using array destructuring
[a, b] = [b, a]
So you would do:
[ this.arr[2*i] , this.arr[i] ] = [ this.arr[i], this.arr[2*i] ]

#5