Learn

Before we can finish the heapifyUp() function we need to do a little background work to establish the structure of the binary tree out of an array. To do this, we’ll use a little math magic with the array indices.

The root of our tree will always be at index 0, and its left child will be index 1 while its right is index 2. The first structure is easy, but now what happens when we add children to the left node? In our array, we place those children at index 3 and 4 four respectively whereas children of the first right node would end up at indices 5 and 6.

If we look closely, we can start seeing a pattern emerge. Every left child index is equal to twice its parent plus 1 and every right child index is twice its parent plus 2. Let’s consolidate the rules:

  • leftChildIndex = (parentIndex * 2) + 1
  • rightChildIndex = (parentIndex * 2) + 2
  • parentIndex = (childIndex - 1) / 2

Since we will be constantly getting and setting values using this logic, we’ve created a series of “help the helper” functions that return these indices. We’ve also included another helper function that checks if our index exists in the array, that way we don’t end up trying to stick a value outside the bounds of the array.

Now that that’s out of the way, let’s finish implementing the heapifyUp() function. The basic functionality of this function will be to iterate from the end of the array where we added a new element and check if the current task we are visiting is closer to today than its parent. If it is, we need to swap those elements and then redo the test on the new parent.

Instructions

1.

Inside the heapifyUp() function create a new variable, currentIndex, equal to the last index of the heap array. You can get the size of the array by referencing the computed property, size.

2.

Create a while statement that checks for two things:

  • The currentIndex is greater than 0 AND
  • The element of heap at currentIndex is less than the element of heap at the parent index of currentIndex. Use the helper function parentIndex(of:) here.

Leave the body of the while empty for now.

3.

Inside the body of the while loop, start by printing the following data so we can see when we’ve had to perform a swap.

"Heapifying (up) elements at index: \(currentIndex) & \(parentIndex(of: currentIndex))"
4.

After the print statement, we need to actually perform the swap. Arrays have the perfect built-in function for this, swapAt(::) that takes two element indexes and swaps the values at those locations. Call the function on heap passing in the currentIndex and the parent of currentIndex as the arguments. Reference the parent index the same way we did in the while loop logic.

5.

At the end of the while loop, still inside it, set the currentIndex equal to the parent index so we can check the next parent/child relationship until we reach the top of the heap.

Uncomment the last lines of code, run it, and look at the output. You can see that we have called our heapifyUp() function and that the heap now has the “Submit Initial Design Ideas” task at the top. You will also notice that when we print an item if the date is older than now it will be printed with “LATE: “ in front of it.

If the program never stops running after hitting “Run”, it’s entered an infinite loop, refresh the browser window, and double check your code to make sure we’ve added the proper logic to exit the while loop.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?