Heapify II: JavaScript

Hey, I’m completing the Heapify II exercise: https://www.codecademy.com/paths/back-end-engineer-career-path/tracks/fscp-complex-data-structures/modules/fecp-heaps/lessons/learn-heaps-javascript/exercises/learn-heaps-javascript-heapify-ii
and am having some difficulty implement the heapify method in step 8. In the previous step, you create a while loop that runs as long as you have a left and right child to swap. Then in #1 of step 8, inside that while you check to see if there is both and a left child and right child. The instructions are as follows:

“In .heapify() at the beginning of the while loop, check to see if leftChild and rightChild both exist. Use the helper method .exists() to check for the existence of an element at a particular index.”

I implemented this with the following code:

heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {

All of the above code except for the if conditional is brought forward from the previous step. My code was not accepted even though I confirmed with the hint that I was following the steps correctly. I decided to check for the answer and found that there was now an additional while loop, nested directly under the original like this:

...
    while (this.canSwap(current, leftChild, rightChild)) {
      while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {

There is no indication in the instructions anywhere in this part of the exercise that another while loop is needed, yet the method will not run correctly without one. I’m not sure if this because of a lack of instructions or if I’m missing something.
Thanks for the help!

Hello,

I checked my completed (and accepted) code for this exercise and my first if statement in the while loop matches what you posted:

  heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
        // ...
      } 
    }
  }

Did you get a specific message when it wasn’t accepted? You only posted part of the code, but I’m assuming you included the closing curly brace for the if statement you added.

I’m not sure what’s going on with the other code you posted. Is that what is shown when you click View Solution after failing the test a couple times?

Hey, the message I got was:

Did you check if both leftChild and rightChild exist using this.exists() inside the while loop in .heapify() ?

There was no error logged in the console.

Here is my full code for the method:

 heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
        leftChild = getLeft(current);
        rightChild = getRight(current);
    }
  }
  }

Yes, the other code with the two while loops is what was shown when I viewed the solution
PS. I copied and pasted your code into the exercise and got the same error. This is after resetting the exercise. I have no idea what’s going on here.

Can you post a link to the complete source? You can generate it using this:

image

Sure, here it is:

class MinHeap {
  constructor() {
    this.heap = [ null ];
    this.size = 0;
  }

  popMin() {
    if (this.size === 0) {
      return null
    }
    console.log(`\n.. Swap ${this.heap[1]} with last element ${this.heap[this.size]}`);
    this.swap(1, this.size);
    const min = this.heap.pop();
    this.size--;
    console.log(`.. Removed ${min} from heap`);
    console.log('..',this.heap);
    return min;
  }

  add(value) {
    console.log(`.. adding ${value}`);
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
    console.log(`added ${value} to heap`, this.heap);
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
      console.log(`.. swap ${this.heap[current]} with parent ${this.heap[getParent(current)]}`);
      this.swap(current, getParent(current));
      console.log('..', this.heap);
      current = getParent(current);
    }
  }

  heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
        // ...
      } 
    }
  }

  exists(index) {
    return index <= this.size;
  }

  canSwap(current, leftChild, rightChild) {
    // Check that one of the possible swap conditions exists
    return (
      this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
      || this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
    );
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

}

const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;

module.exports = MinHeap;

I reset my exercise to help test it out.

This is what my heapify() method looked like immediately after the reset:

  heapify() {
    console.log('Heapify');
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      leftChild = getLeft(current);
      rightChild = getRight(current);
    }
  }

I added the if statement, hit Run, and the code was accepted. This is what it looked like:

  heapify() {
    console.log('Heapify');
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
  
      } 
      leftChild = getLeft(current);
      rightChild = getRight(current);
    }
  }

When the code is reset, I’m not sure if it’s doing it by copying over our previous code again or by pulling from a standard file. I do notice that when I reset, the console.log() command at the top of heapify() is included whereas each time you’ve posted after a reset never included it.

Ok, so I found the issue.

while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
       leftChild = getLeft(current);
       rightChild = getRight(current);
      }
    }
  }

I was updating leftChild and rightChild inside the if block, thats the problem. Even though my if statement evaluating the condition is correct, I will get an error that I didn’t do it correctly because the if block should be empty, though this isn’t mentioned in the error message: " Did you check if both leftChild and rightChild exist using this.exists() inside the while loop in .heapify() ?"
I think this should be changed, I was stuck on this for a while because the error code I was receiving was not actually expressing the real problem with my code.

True, not all of their test messages are very clear and some of their tests are extra picky. It probably depends on the method by which they were testing that the code was included here. I imagine it’s very difficult to test for every scenario in a learning environment like this when users could interpret the instructions in a number of ways. Having an error message that acknowledged the if statement was added but something else was changed that shouldn’t have been would have been nice.

At least you’re through this one.

1 Like

It’s hard to anticipate and cover any problematic coding that won’t give an error but doesn’t fit the goals of the exercise. Anyways, thanks for your help in working through this!