Data Structures: Remove an Element from a Max Heap remove() method fails on test

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

The test includes the clause “while maintaining the max heap property”.

Running your code, I get output such as:
image
In the second line, the heap no longer satisfies the max heap property. Branching to the right, you have a 6 node with 30 and 42 as children.

Thanks for help
Now I corrected the method. All childNode less than its parent…
I also made a quick draw method… Its help to understand the relationship…
But still fails on the test… Maybe because the smallest Node (6) is on right side and not on the left?

corrected 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[currentIndex] = currentChildNode;
            this.heap[currentChildIndex] = currentNode;
            currentIndex = currentChildIndex;
            [left, right] = [2 * currentIndex, 2 * currentIndex + 1]
            currentChildIndex = this.heap[right] && this.heap[right].value > this.heap[left].value 
                ? right
                : left
        ;
        }
        return toRemove;
    };
    
    draw(index = 1) {
        if (index < this.heap.length) {
            if (index > 1) {
                let children = " ";
                let childGap = " ";
                for (let i = 0; i < this.heap.length / 2 - index; i ++) {
                    childGap += " ";
                }
                for (let i = 0; i < index; i ++) {
                    if (this.heap[index + i] !== undefined) {
                        children += childGap + this.heap[index + i].value;
                    }
                }
                console.log(children);
            } else {
                let firstGap = " ";
                for (let i = 0; i < this.heap.length / 2 - index; i ++) {
                    firstGap += " ";
                }
                console.log(" ", firstGap, this.heap[index].value);
            }
            this.draw(index * 2);
        }
    };
};

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);
myMaxHeap.insert(27);
myMaxHeap.insert(88);
myMaxHeap.insert(61);
console.log(myMaxHeap);
console.log(myMaxHeap.remove());
myMaxHeap.draw();
console.log(myMaxHeap.remove());
myMaxHeap.draw();
////console.log(myMaxHeap.print());
console.log(myMaxHeap.remove());
myMaxHeap.draw();
console.log(myMaxHeap.remove());
myMaxHeap.draw();
//console.log(myMaxHeap.remove());
//console.log(myMaxHeap.remove());
//console.log(myMaxHeap.remove());
//console.log(myMaxHeap.remove());
//console.log(myMaxHeap.remove());