Data Structures - Remove an Element from a Max Heap

[jacques.nikola]

Tell us what’s happening:

It looks like my method fits all of the requirements but the tests still fail. I have checked all the posts about this issue and that allowed me to also account for cases where the heap has only one element in it or is empty (if the heap is empty, returns null) but it didn’t help.

Your code so far

const MaxHeap = function () {
  this.heap = [];
  this.parent = index => {
    return Math.floor((index - 1) / 2);
  }
  this.insert = element => {
    this.heap.push(element);
    this.heapifyUp(this.heap.length - 1);
  }
  this.heapifyUp = index => {
    let currentIndex = index,
    parentIndex = this.parent(currentIndex);
    while (currentIndex > 0 && this.heap[currentIndex] > this.heap[parentIndex]) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = this.parent(parentIndex);
    }
  }
  this.swap = (index1, index2) => {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }
  this.print = () => {
    return this.heap;
  }
  // Only change code below this line
  this.remove = () => {
        if (this.heap.length===0) return null;
        const element = this.heap.pop();
        if (this.heap.length===0) return element;
        const removedElement = this.heap[0];
        this.heap[0] = element;
        const searchHeap = (element) => {
            const parentIndex = this.heap.indexOf(element);
            if (this.heap.length>(parentIndex*2+1)){
                const firstChild = this.heap[parentIndex*2+1];
                const secondChild = this.heap[parentIndex*2+2]?this.heap[parentIndex*2+2]:null;
                const maxChildIndex = this.heap.indexOf(Math.max(firstChild,secondChild));
                if (this.heap[maxChildIndex]>this.heap[parentIndex]){
                    let parentCopy = this.heap[parentIndex];
                    this.heap[parentIndex] = this.heap[maxChildIndex];
                    this.heap[maxChildIndex] = parentCopy;
                }
                searchHeap(firstChild);
                secondChild?searchHeap(secondChild):null;
            };
        }
        searchHeap(element);
        return removedElement;
    }
  // Only change code above this line
};

const mh = new MaxHeap();
mh.insert(6);
mh.insert(22);
mh.insert(30);
mh.insert(37);
mh.insert(63);
mh.insert(48);
mh.insert(42);
mh.insert(76);
console.log(mh.print());
console.log(mh.remove());
console.log(mh.print());

Output:

[ 76, 63, 48, 37, 30, 22, 42, 6 ]
76
[ 63, 37, 48, 6, 30, 22, 42 ]

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36

Challenge: Data Structures - Remove an Element from a Max Heap

Link to the challenge:

freeCodeCamp.org

[yunsuklee]

I believe your output is fine actually. The output that makes the test pass is the following:

[ 63, 48, 30, 37, 6, 22, 42 ]

But if I’m not wrong that is not a max heap’s array…
Let’s see if someone more experienced can help.

[jacques.nikola]

Thanks for your reply. You’re right, 42 should not be a child of 30. It doesn’t fit the definition of max heap:

A max heap is a complete binary tree in which the value of a node is greater than or equal to the values of its children.

Just out of curiosity, where did you find the test code?

[jacques.nikola]

My remove method wasn’t correct, in the example above it worked but when I used it in the following challenge on random arrays it didn’t always produce the correct result.

Here is the correct version:

    this.remove = () => {
        const element = this.heap.pop();
        if (this.heap.length===0) return element;
        const removedElement = this.heap[0];
        this.heap[0] = element;
        let parentIndex = 0;
        while(parentIndex*2+1 < this.heap.length){
            const firstChild = this.heap[parentIndex*2+1];
            const secondChild = this.heap[parentIndex*2+2]?this.heap[parentIndex*2+2]:null;
            const maxChildIndex = this.heap.indexOf(Math.max(firstChild,secondChild));
            if (this.heap[maxChildIndex]>this.heap[parentIndex]){
                let parentCopy = this.heap[parentIndex];
                this.heap[parentIndex] = this.heap[maxChildIndex];
                this.heap[maxChildIndex] = parentCopy;
            }
            parentIndex++;
        }
        return removedElement;
    }

However, now I’m puzzled about that test assertion you mentioned in your post